题解 P3440 【[POI2006]SZK-Schools】
oscar
2017-10-04 01:12:13
【POI补全计划#24 POI2006 SZK】
没什么可说的,又是标准的费用流(看数据范围都知道)
建图分三部分:
1.源点S->学校i,容量1,费用0
2.学校i->可接受编号j,容量1,费用 $ | m_i - j | \times t_i $,其中 $ a_i \leq j \leq b_i $
3.编号i->汇点T
然后再这个图上跑最小费用最大流即可
贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=510,S=501,T=502,SHIFT=250;
struct edge
{
int v,f,len;
edge *next,*rev;
}*h[MAXN],pool[MAXN*MAXN*2];
int top;
inline void addedge(int u,int v,int c,int w)
{
edge *tmp=&pool[++top];tmp->v=v;tmp->f=c;tmp->len=w;tmp->next=h[u];h[u]=tmp;
edge *pmt=&pool[++top];pmt->v=u;pmt->f=0;pmt->len=-w;pmt->next=h[v];h[v]=pmt;
tmp->rev=pmt;pmt->rev=tmp;
}
int totf,totc;
queue<int> q;
int inq[MAXN],dis[MAXN],last[MAXN];
edge *laste[MAXN];
inline int spfa()
{
while(!q.empty())q.pop();
memset(dis,0x3f,sizeof(dis));
memset(last,0,sizeof(last));
memset(laste,0,sizeof(laste));
dis[S]=0;inq[S]=1;
q.push(S);
while(!q.empty())
{
int u=q.front();q.pop();
inq[u]=0;
for(edge *tmp=h[u];tmp;tmp=tmp->next)
{
if(tmp->f&&dis[tmp->v]>dis[u]+tmp->len)
{
dis[tmp->v]=dis[u]+tmp->len;
last[tmp->v]=u;
laste[tmp->v]=tmp;
if(!inq[tmp->v])
{
inq[tmp->v]=1;
q.push(tmp->v);
}
}
}
}
if(dis[T]==0x3f3f3f3f)return -1;
int cur=T;
while(cur!=S)
{
laste[cur]->f--;laste[cur]->rev->f++;
cur=last[cur];
}
return dis[T];
}
int main()
{
int n;
scanf("%d",&n);
int m,l,r,t;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&m,&l,&r,&t);
addedge(S,i,1,0);
for(int j=l;j<=r;j++)
{
addedge(i,j+SHIFT,1,abs(m-j)*t);
}
addedge(i+SHIFT,T,1,0);
}
int tmp;
while((tmp=spfa())!=-1)
{
totf++;
totc+=tmp;
}
if(totf==n)printf("%d\n",totc);
else printf("NIE\n");
return 0;
}
```