網(wǎng)絡(luò)流

1273 Drainage Ditches

這是一道比較單純的網(wǎng)絡(luò)流，題目要求只要求出源點(diǎn)到匯點(diǎn)的最大流就行了，而并不需要任何的建模抽象的東西，唯一一點(diǎn)要注意的是，要考慮有重邊的情況。

這里我用的是增廣路法求的最大流，流從源點(diǎn)s出發(fā)，用BFS找到一條增廣路徑，然后找這條路徑上的最小值min，對(duì)增廣路進(jìn)行擴(kuò)展，每一次擴(kuò)展會(huì)使得f[pre[i]][i]的值增大，那么它的反向路徑f[i][pre[i]]的值會(huì)減小，一直進(jìn)行下去，直到找不到增廣路為止，算法結(jié)束。

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

       也是一道很經(jīng)典的網(wǎng)絡(luò)流的題目，題目大意是Mirko有M個(gè)豬圈，豬圈里面有一定數(shù)量的豬，但他沒有鑰匙，而只有來買豬的顧客才會(huì)有一些特定房間的鑰匙，每次顧客來之前，都跟Mirko預(yù)約好，所以Mirko的任務(wù)就是找出一個(gè)計(jì)劃，使他能賣出最多數(shù)量的豬。對(duì)于每位顧客，Mirko可以選擇賣出豬的數(shù)量，也可以在該顧客打開的豬圈間任意調(diào)整豬的數(shù)量，每個(gè)豬圈的容量無(wú)限大。

       我覺得這個(gè)問題的一個(gè)關(guān)鍵點(diǎn)是建模，如何建立一個(gè)網(wǎng)絡(luò)流的模型很關(guān)鍵。我把所有的豬圈統(tǒng)一看成一個(gè)大的源點(diǎn)S，把每個(gè)顧客看成是一個(gè)節(jié)點(diǎn)，然后再人工地添加一個(gè)匯點(diǎn)。這樣可以得出下面的路徑關(guān)系。

1、 在先到的顧客和后到的顧客之間有一條路徑，指向后到的顧客，這條路徑的容量無(wú)限大。

2、 在源點(diǎn)有指向各個(gè)顧客的路徑，路徑的容量為顧客擁有的鑰匙所能打開的豬圈的豬的總量，注意，當(dāng)兩個(gè)顧客擁有同一把鑰匙的時(shí)候，豬圈的數(shù)量只能加到一個(gè)顧客節(jié)點(diǎn)的路徑上，不能重復(fù)加，他們之間的轉(zhuǎn)移關(guān)系就靠1中兩顧客間容量無(wú)限大的路徑來實(shí)現(xiàn)。

我想有了這兩點(diǎn)，把網(wǎng)絡(luò)流的模型建立起來后，求解的算法按照1273的模版就應(yīng)該很容易了。

#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;

       //將豬圈看作一個(gè)大的源點(diǎn)0，再外加一個(gè)匯點(diǎn)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);                         //每位顧客擁有鑰匙的數(shù)量

                     for(j=1; j<=c; j++)

                     {

                            scanf("%d",&p);                  //輸入每把鑰匙的編號(hào)

                            f[0][i]+=pig[p];

                            key[p][i]=1;

                            pig[p]=0;

                     }

                     scanf("%d",&c);                         //輸入每位顧客需要豬的數(shù)量

                     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;    

}