網絡流
1273 Drainage Ditches
這是一道比較單純的網絡流，題目要求只要求出源點到匯點的最大流就行了，而并不需要任何的建模抽象的東西，唯一一點要注意的是，要考慮有重邊的情況。
這里我用的是增廣路法求的最大流，流從源點s出發，用BFS找到一條增廣路徑，然后找這條路徑上的最小值min，對增廣路進行擴展，每一次擴展會使得f[pre[i]][i]的值增大，那么它的反向路徑f[i][pre[i]]的值會減小，一直進行下去，直到找不到增廣路為止，算法結束。
Source
Problem Id:1273 User Id:linyangfei
Memory:240K Time:15MS
Language:C++ Result:Accepted
Source
#include <stdio.h>
#include <string.h>
int n,m,pre[205];
int f[205][205];
bool mark[205];
int bfs();
__int64 MaxFlow();
int main()
{
int i,s,e,c;
//freopen("1273.in","r",stdin);
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(f,0,sizeof(f));
for(i=0; i<m; i++)
{
scanf("%d%d%d",&s,&e,&c);
if(f[s-1][e-1]==0)
f[s-1][e-1]=c;
else
f[s-1][e-1]+=c;
}
printf("%I64d\n",MaxFlow());
}
return 0;
}
int bfs()
{
int q[205],qt=0,qh=1,i,x,min;
q[qt]=0;
mark[0]=true;
while(qt<qh)
{
x=q[qt];
if(x==n-1)
{
min=100000000;
for(i=n-1; pre[i]!=-1; i=pre[i])
min=f[pre[i]][i]<min?f[pre[i]][i]:min;
return min;
}
for(i=1; i<n; i++)
{
if(!mark[i] && f[x][i]>0)
{
q[qh++]=i;
mark[i]=true;
pre[i]=x;
}
}
qt++;
}
return 0;
}
__int64 MaxFlow()
{
int i,min;
__int64 maxflow=0;
memset(mark,0,sizeof(mark));
for(i=0; i<n; i++)
pre[i]=-1;
while(min=bfs())
{
for(i=n-1; pre[i]!=-1; i=pre[i])
{
f[pre[i]][i]-=min;
f[i][pre[i]]+=min;
}
maxflow+=min;
memset(mark,0,sizeof(mark));
for(i=0; i<n; i++)
pre[i]=-1;
}
return maxflow;
}
1149 PIGS
也是一道很經典的網絡流的題目，題目大意是Mirko有M個豬圈，豬圈里面有一定數量的豬，但他沒有鑰匙，而只有來買豬的顧客才會有一些特定房間的鑰匙，每次顧客來之前，都跟Mirko預約好，所以Mirko的任務就是找出一個計劃，使他能賣出最多數量的豬。對于每位顧客，Mirko可以選擇賣出豬的數量，也可以在該顧客打開的豬圈間任意調整豬的數量，每個豬圈的容量無限大。
我覺得這個問題的一個關鍵點是建模，如何建立一個網絡流的模型很關鍵。我把所有的豬圈統一看成一個大的源點S，把每個顧客看成是一個節點，然后再人工地添加一個匯點。這樣可以得出下面的路徑關系。
1、 在先到的顧客和后到的顧客之間有一條路徑，指向后到的顧客，這條路徑的容量無限大。
2、 在源點有指向各個顧客的路徑，路徑的容量為顧客擁有的鑰匙所能打開的豬圈的豬的總量，注意，當兩個顧客擁有同一把鑰匙的時候，豬圈的數量只能加到一個顧客節點的路徑上，不能重復加，他們之間的轉移關系就靠1中兩顧客間容量無限大的路徑來實現。
我想有了這兩點，把網絡流的模型建立起來后，求解的算法按照1273的模版就應該很容易了。
#include <stdio.h>
#include <string.h>
const int INF=100000000;
int f[105][105],pig[1005],key[1005][105],pre[105];
bool mark[105];
int m,n;
int bfs();
int MaxFlow();
int main()
{
int i,j,c,p,k;
//將豬圈看作一個大的源點0，再外加一個匯點n+1
freopen("1149.txt","r",stdin);
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=1; i<=m; i++)
scanf("%d",&pig[i]);
memset(f,0,sizeof(f));
memset(key,0,sizeof(key));
for(i=1; i<=n; i++)
{
scanf("%d",&c); //每位顧客擁有鑰匙的數量
for(j=1; j<=c; j++)
{
scanf("%d",&p); //輸入每把鑰匙的編號
f[0][i]+=pig[p];
key[p][i]=1;
pig[p]=0;
}
scanf("%d",&c); //輸入每位顧客需要豬的數量
f[i][n+1]=c;
}
for(i=1; i<=m; i++)
for(j=1; j<=n; j++)
{
if(key[i][j])
for(k=j+1; k<=n; k++)
{
if(key[i][k])
f[j][k]=INF;
}
}
printf("%d\n",MaxFlow());
}
return 0;
}
int bfs()
{
int q[205],qt=0,qh=1,i,x,min;
q[qt]=0;
mark[0]=true;
while(qt<qh)
{
x=q[qt];
if(x==n+1)
{
min=100000000;
for(i=n+1; pre[i]!=-1; i=pre[i])
min=f[pre[i]][i]<min?f[pre[i]][i]:min;
return min;
}
for(i=1; i<=n+1; i++)
{
if(!mark[i] && f[x][i]>0)
{
q[qh++]=i;
mark[i]=true;
pre[i]=x;
}
}
qt++;
}
return 0;
}
int MaxFlow()
{
int i,min;
int maxflow=0;
memset(mark,0,sizeof(mark));
for(i=0; i<=n+1; i++)
pre[i]=-1;
while(min=bfs())
{
for(i=n+1; pre[i]!=-1; i=pre[i])
{
f[pre[i]][i]-=min;
f[i][pre[i]]+=min;
}
maxflow+=min;
memset(mark,0,sizeof(mark));
for(i=0; i<=n+1; i++)
pre[i]=-1;
}
return maxflow;
}
posted on 2007-09-22 17:09
飛飛 閱讀(860)
評論(2) 編輯 收藏 引用 所屬分類:
ACM/ICPC