http://acm.pku.edu.cn/JudgeOnline/problem?id=1149網絡流
挺不錯的，剛開始想直接把pig-houses搞到圖里面去，發現那樣的話st網絡會變成m+n+2<=1000+100+2 太恐怖了
上網查了一下，學會了簡化建圖，把豬圈簡化掉，這樣不會改變約束條件
注意顧客的先后條件
主要是建圖，看不懂的話可以和我交流
推薦帖子：
http://imlazy.ycool.com/post.2059102.html
#include<iostream>
using namespace std;
#define MAXN 104
#define MAXM 1001
//求網絡最大流,鄰接陣形式
//返回最大流量,flow返回每條邊的流量
//傳入網絡節點數n,容量mat,源點source,匯點sink
// 測試過了
#define inf 1000000000
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN])
{
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (j=i=0;i<n;j+=flow[source][i++]);
return j;
}
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int h[MAXM];
int hash[MAXM];
int main()
{
int m,n,s,t;
int k,tmp,b;
int c=0;
memset(mat,0,sizeof(mat));
memset(h,0,sizeof(h));
memset(hash,0,sizeof(hash));
scanf("%d%d",&m,&n);
s=0;t=n+1;//總共n+2個點
for(int i=1;i<=m;i++){
scanf("%d",&h[i]);
//mat[s][i]=h[i];
c+=h[i];
}
for(int i=1;i<=n;i++){
scanf("%d",&k);
for(int j=0;j<k;j++){
scanf("%d",&tmp);
if(hash[tmp]==0){
mat[s][i]+=h[tmp];
hash[tmp]=i;
}
else{
mat[hash[tmp]][i]=c;
// hash[tmp]=i;
}
}
scanf("%d",&b);
mat[i][t]=b;
}
printf("%d\n",max_flow(n+2,mat,s,t,flow));
// system("pause");
return 0;
}
posted on 2009-02-25 21:46
爬 閱讀(1763)
評論(0) 編輯 收藏 引用 所屬分類:
pku