[SDOI2011]工作安排 BZOJ2245

分析:

费用流裸题,按照题面要求建边就可以了,语文题,我读了10多分钟才知道这题干啥...特别是注意一个细节a[j+1]-a[j]...

附上代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 555
#define S 0
#define T 550
struct node
{
int to,next,val,flow,from;
}e[N*N<<5];
int head[N],cnt,vis[N],from[N],n,m,map[N][N],s[N],a[N];long long ans,dis[N];
void add(int x,int y,int z,int f){e[cnt].to=y;e[cnt].next=head[x];e[cnt].from=x;e[cnt].val=z;e[cnt].flow=f;head[x]=cnt++;}
void insert(int x,int y,int z,int f){add(x,y,z,f);add(y,x,-z,0);}
int spfa()
{
memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));memset(from,-1,sizeof(from));
queue <int>q;q.push(S);dis[S]=0;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(dis[to1]>dis[x]+e[i].val&&e[i].flow)
{
from[to1]=i;
dis[to1]=dis[x]+e[i].val;
if(!vis[to1])vis[to1]=1,q.push(to1);
}
}
}
return dis[T]==0x3f3f3f3f3f3f3f3f?0:1;
}
void mcf()
{
int i=from[T],x=1<<30;
while(i!=-1)
{
x=min(x,e[i].flow);
i=from[e[i].from];
}
i=from[T];
while(i!=-1)
{
e[i].flow-=x,e[i^1].flow+=x;ans+=e[i].val*x;
i=from[e[i].from];
}
return ;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
insert(i+m,T,0,x);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
if(x)insert(i,j+m,0,1<<30);
}
}
for(int i=1;i<=m;i++)
{
scanf("%d",&s[i]);
for(int j=1;j<=s[i];j++)
{
scanf("%d",&a[j]);
}
a[s[i]+1]=1<<30;
for(int j=0;j<=s[i];j++)
{
int x;
scanf("%d",&x);
insert(S,i,x,a[j+1]-a[j]);
}
}
while(spfa())mcf();
printf("%lld\n",ans);
return 0;
}

  

上一篇:linux命令——scp 两台linux机器间文件或目录传输


下一篇:Android Native jni 编程入门