hdu 3572 最大流isap模版 邻接表写。。
- 题意：用m个机器，处理n个任务，每个任务必须在[si,ei]时间段完成，需要pi天才能完成。每个机器只能处理一个任务，
- 即每天只能处理m个任务。
- 题解：可以采用贪心法处理，区间覆盖问题，可以参见刘汝佳的书。
- 或者采用最大流，建图：把每个任务和每一天看做一个点，增加源点s和汇点t，在s和每个任务之间连一条边，容量为持续
- 天数；在每一天和t之间连一条边，容量为m；在每个任务和对应天数之间连一条边，容量为1。然后最大流量即为所求。
#include<stdio.h>
#include<string.h>
#define INF 1<<29;
int m,n,ds;
const int maxd 10010;
const int maxb 100010;//注意此处单边乘2 双向边乘4int h[1010],vh[1010],flo,flag,cf_path,he[1010],nu;struct ss{ int v,ne,s;}st[505000];int source,sink;//起点 终点void sap(){ nu=0; memset(he,-1,sizeof(he)); memset(st,0,sizeof(st)); memset(vh,0,sizeof(vh)); memset(h,0,sizeof(h));}void add(int hea,int v,int s){ st[nu].ne=he[hea]; st[nu].v=v; st[nu].s=s; he[hea]=nu++; st[nu].ne=he[v]; st[nu].v=hea; st[nu].s=0; he[v]=nu++;}int dfs(int pos,int cost,int cnt){ if (pos==sink) { return cost; } int j,minh=cnt-1,lv=cost,d; for(j=he[pos];j!=-1;j=st[j].ne) { int v=st[j].v,val=st[j].s; if(val>0) { if (h[v]+1==h[pos]) { if (lv<st[j].s) d=lv; else d=st[j].s; d=dfs(v,d,cnt); st[j].s-=d; st[j^1].s+=d; lv-=d; if (h[source]>=cnt) return cost-lv; if (lv==0) break; } if(h[v]<minh) minh=h[v]; } } if(lv==cost) { --vh[h[pos]]; if(vh[h[pos]]==0) h[source]=cnt; h[pos]=minh+1; ++vh[h[pos]]; } return cost-lv;}int maxflow(int st,int ed,int cnt){ source=st; sink=ed; int ret=0; memset(vh,0,sizeof(vh)); memset(h,0,sizeof(h)); int maxx=10000; vh[st]=cnt; while(h[st]<cnt) { ret+=dfs(st,maxx,cnt); } return ret;}int main(){ int a,b; scanf("%d",&a); int cas=0; while(a--) { sap(); scanf("%d%d",&m,&n); ds=2; int i,j,x,y,z,ii,max=0,all=0; int min=INF; for(i=1;i<=m;i++) { ds++; scanf("%d%d%d",&x,&y,&z); all+=x; add(0,i,x); for(ii=y;ii<=z;ii++) {add(i,ii+m,1);} if(z>max) max=z; if(y<min) min=y; } ds+=max-min+1; for(i=1;i<=max;i++) add(i+m,1004,n); if(maxflow(0,1004,ds)==all) printf("Case %d: Yes\n",++cas); else printf("Case %d: No\n",++cas); printf("\n"); } return 0;}智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。