「JoyOI1431」分配任务
描述 Description
随着JoyOI发展越来越大，管理员的任务越来越重，如何合理的分配任务，成为了一个可研究的命题。JoyOI当前一共有M个需要做的任务，和N位管理员。每一个管理员的上线时间并不是固定的，每一个人有d[i]单位的上线时间，每一位管理员一个单位的时间可以完成一个任务，且一个任务只能由一个管理员来完成（如果更多的管理员参与进来，可能会造成混乱）。每一位管理员的能力有所不同，所以能完成的任务集合可能不相同。最终让所有未完成的任务数量最少。
输入格式 InputFormat
输入文件第一有两个正整数，分别是N和M
下面面N行，每一行表示一位管理员的信息，第一个正整数为d[i]，第二个正整数为tot，后面有tot个数，表示第i位管理员可以完成的任务集合。
输出格式 OutputFormat
输出文件仅有一个数，所有未完成任务的最少值。
数据范围和注释 Hint
数据范围约定：
20%的数据 n<=10 M<=10 且D[i]=1
60%的数据 n<=50 M<=300 且D[i]<=30
100%的数据 n<=3000 M<=10000 且d[i]<=100
题解
源点向所有管理员连d[i]的边
管理员向可解决的任务连1的边
任务向汇点连1的边
ans=m-最大流
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<iostream> #include<cstdio> #include<cstring> #define T 13001 #define inf 0x7fffffff using namespace std; int n,m,ans,cnt=1; int head[13005],h[13005]; struct data{int to,next,v;}e[8000001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} bool bfs() { int q[13005],t=0,w=1,i,now; memset(h,-1,sizeof(h)); q[0]=h[0]=0; while(t!=w) { now=q[t];t++;if(t==13001)t=0; i=head[now]; while(i) { if(e[i].v&&h[e[i].to]<0) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==13001)w=0;} i=e[i].next; } } if(h[T]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==T)return f; int i=head[x],w,used=0; while(i) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w; e[i^1].v+=w; used+=w; if(used==f)return f; } i=e[i].next; } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())ans+=dfs(0,inf);} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int t,x;scanf("%d",&t); insert(0,i,t); scanf("%d",&t); for(int j=1;j<=t;j++) { scanf("%d",&x); insert(i,n+x,1); } } for(int i=1;i<=m;i++) insert(n+i,T,1); dinic(); printf("%d",m-ans); return 0; } |
Subscribe