soj 3109最小切割最大流
2010-08-31 11:33
DescriptionW教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。 Input输入包含多组测试数据,每组数据第1行有2个正整数m和n。m是实验数,n是仪器数。 Output每组数据输出一行,为净收益。 Sample Input2 3 Sample Output17 Source经典问题
#define N 105 #define inf 100000000 #include<iostream> #include<stdio.h> #include<string.h> using namespace std; int cap[N][N],pre[N]; int n,m,st,en; bool bfs() { memset(pre,-1,sizeof(pre)); pre[st]=0; int q[N+10],head=0,end=1,i; q[0]=st; while(head<end) { int u=q[head++]; for(i=0;i<=en;i++) if(pre[i]==-1&&cap[u][i]>0) { pre[i]=u; if(i==en) return 1; q[end++]=i; } } return 0; } int max_flow() { int ans=0; while(bfs()) { int minflow=inf; int u=en; while(u!=st) { if(minflow>cap[pre[u]][u]) minflow=cap[pre[u]][u]; u=pre[u]; } u=en; ans+=minflow; while(u!=st) { cap[pre[u]][u]-=minflow; cap[u][pre[u]]+=minflow; u=pre[u]; } } return ans; } int main() { while(cin>>n>>m) { int i,j,sum=0; st=0; en=n+m+1; memset(cap,0,sizeof(cap)); for(i=1;i<=n;i++) { int get,tmp; char c; scanf("%d",&get); sum+=get; cap[i+m][en]=get; while(scanf("%d%c",&tmp,&c)) { cap[tmp][i+m]=inf; if(c=='\n') break; } } for(i=1;i<=m;i++) { int cost; scanf("%d",&cost); cap[st][i]=cost; } printf("%d\n",sum-max_flow()); } return 0; } |
来源: http://hi.baidu.com/lerroy312/blog/item/857bf51c4839f50935fa41e0.html