11. 运输问题1

★★☆   输入文件：maxflowa.in   输出文件：maxflowa.out   简单对比

时间限制：1 s   内存限制：128 MB

【问题描述】

    一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。请你计算，在不考虑其它车辆使用公路的前提下，如何充分利用所有的公路，使产地运输到销地的商品最多，最多能运输多少商品。

【输入格式】

输入文件有若干行

第一行，一个整数n，表示共有n个城市$(2 \leq n \leq 100)$,产地是1号城市，销地是n号城市。

下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且该数字表示该公路流量。

【输出格式】

输出文件有一行

第一行，1个整数max，表示最大流量为max。

【输入输出样例】

输入文件名： maxflowa.in

6

0 4 8 0 0 0

0 0 4 4 1 0

0 0 0 2 2 0

0 0 0 0 0 7

0 0 0 6 0 9

0 0 0 0 0 0

输出文件名：maxflowa.out

8

好了对于这么水的题我表示只是来存代码的(逃

注意读入建图的时候的反向边标记然后大力Dinic就好了w

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 8 const int MAXV=110; 9 const int MAXE=10010; 10 const int INF=0x7FFFFFFF; 11 12 struct Edge{ 13 int from; 14 int to; 15 int flow; 16 Edge* rev; 17 Edge* next; 18 }; 19 Edge E[MAXE]; 20 Edge* head[MAXV]; 21 Edge* top=E; 22 23 int v; 24 int depth[MAXV]; 25 int flow[MAXV][MAXV]; 26 27 int Dinic(int,int); 28 void Initialize(); 29 void Insert(int,int); 30 int DFS(int,int,int); 31 bool BFS(int,int); 32 33 int main(){ 34 freopen("maxflowa.in","r",stdin); 35 freopen("maxflowa.out","w",stdout); 36 Initialize(); 37 printf("%d\n",Dinic(1,v)); 38 return 0; 39 } 40 41 int Dinic(int s,int t){ 42 int ans=0; 43 while(BFS(s,t)){ 44 ans+=DFS(s,INF,t); 45 } 46 return ans; 47 } 48 49 int DFS(int s,int flow,int t){ 50 if(s==t||flow==0) 51 return flow; 52 int tmp=flow; 53 int k; 54 for(Edge* i=head[s];i!=NULL;i=i->next){ 55 if(i->flow!=0&&tmp!=0&&depth[i->to]==depth[s]+1){ 56 k=DFS(i->to,std::min(tmp,i->flow),t); 57 if(k==0){ 58 depth[i->to]=0; 59 continue; 60 } 61 tmp-=k; 62 i->flow-=k; 63 i->rev->flow+=k; 64 if(tmp==0) 65 break; 66 } 67 } 68 return flow-tmp; 69 } 70 71 bool BFS(int s,int t){ 72 memset(depth,0,sizeof(depth)); 73 std::queue
            
              q; 74 depth[s]=1; 75 q.push(s); 76 while(!q.empty()){ 77 s=q.front(); 78 q.pop(); 79 for(Edge* i=head[s];i!=NULL;i=i->next){ 80 if(depth[i->to]==0&&i->flow!=0){ 81 q.push(i->to); 82 depth[i->to]=depth[s]+1; 83 if(i->to==t) 84 return true; 85 } 86 } 87 } 88 return false; 89 } 90 91 void Initialize(){ 92 scanf("%d",&v); 93 for(int i=1;i<=v;i++){ 94 for(int j=1;j<=v;j++){ 95 scanf("%d",&flow[i][j]); 96 } 97 } 98 for(int i=1;i<=v;i++){ 99 for(int j=1;j
             
              from=a;107 top->to=b;108 top->flow=flow[a][b];109 top->next=head[a];110 head[a]=top;111 top->rev=top+1;112 top++;113 top->from=b;114 top->to=a;115 top->flow=flow[b][a];116 top->next=head[b];117 head[b]=top;118 top->rev=top-1;119 top++;120 }