POJ 1459

  1 #include<iostream>
  2 #define MAXN 105
  3 #include"queue"
  4 #define big_num 100000000
  5 using namespace std;
  6 
  7 int _m[MAXN][MAXN];
  8 int Ford_fulkerson(int n, int s, int t, int &F,int g[][MAXN]);
  9 int main()
 10 {
 11     //freopen("acm.acm","r",stdin);
 12     int point;
 13     int np;
 14     int nc;
 15     int edge;
 16     char left;
 17     char right;
 18     char space;
 19     int flow;
 20     int u;
 21     int v;
 22     int i;
 23     int node;
 24     while(cin>>point>>np>>nc>>edge)
 25     {
 26         memset(_m,0,sizeof(_m));
 27         for(i = 0; i < edge; ++ i)
 28         {
 29             cin>>left;
 30             cin>>u;
 31             cin>>space;
 32             cin>>v;
 33             cin>>right;
 34             cin>>flow;
 35             ++ u;
 36             ++ v;
 37             _m[u][v] = flow;
 38         }
 39         for(i = 0; i < np; ++ i)
 40         {
 41             cin>>left;
 42             cin>>u;
 43             cin>>right;
 44             cin>>flow;
 45             ++ u;
 46             _m[0][u] = flow;
 47         }
 48         for(i = 0; i < nc; ++ i)
 49         {
 50             cin>>left; 
 51             cin>>u;
 52             cin>>right;
 53             cin>>flow;
 54             ++ u;
 55             _m[u][point+1] = flow;
 56         }
 57         int F = 0;
 58         while(Ford_fulkerson(point+2,0,point + 1,F,_m));        
 59         cout<<F<<endl;
 60     }
 61 }
 62 
 63 
 64 
 65 int find_path(int m, int s,int t,int pre[MAXN],int g[][MAXN])
 66 {
 67     queue<int> q;        
 68     int * mark = new int[m];
 69     memset(mark,0,sizeof(int)*m);
 70     int x;
 71     mark[s] = 1;               
 72     int i;
 73     q.push(s);                   
 74     while(!q.empty())        
 75     {
 76         x = q.front();            
 77         for(i = 0; i < m; i++)
 78         {
 79             if(g[x][i] > 0 && mark[i] == 0)
 80             {                        
 81                 mark[i] = 1;
 82                 pre[i] = x;    
 83                 if(i == t)            
 84                     return 1;
 85                 q.push(i);        
 86             }
 87         }
 88     q.pop();
 89     }
 90     delete [] mark;
 91     return 0;
 92 }
 93 int Ford_fulkerson(int n, int s, int t, int &F,int g[][MAXN])
 94 {
 95     int i;
 96     int min;
 97     int * pre = new int[n];                    
 98     if(find_path(n,s,t,pre, g) == 0)
 99     {
100         delete [] pre;
101         return 0;
102     }
103     min = big_num;                
104     for(i = t; i != s; i = pre[i])
105         if(g[pre[i]][i] < min)
106         {
107             min = g[pre[i]][i];
108         }
109     for(i = t; i != s; i = pre[i])
110     {
111         g[pre[i]][i] -= min;
112         g[i][pre[i]] += min;
113     }
114     F += min;    
115     delete []pre;
116     return 1;
117 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com