1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int G[300][300]; 5 int Prev[300]; //路径上每个节点的前驱节点 6 bool Visited[300];  7 int n,m;  //m是顶点数目，顶点编号从1开始 1是源，m是汇, n是 边数 8  9 int Augment()10 {  11     int v;12     int i;13     deque
       
         q;14     memset(Prev,0,sizeof(Prev));15     memset(Visited,0,sizeof(Visited));16     Prev[1] = 0;17     Visited[1] = 1;18     q.push_back(1);19     bool bFindPath = false;20   //用bfs寻找一条源到汇的可行路径 21     while (!q.empty())22     {23         v = q.front();24         q.pop_front();25         for (i = 1; i <= m; i++)26         {27             if (G[v][i] > 0 && Visited[i] == 0)28             {   29                 //必须是依然有容量的边，才可以走30                 Prev[i] = v;31                 Visited[i] = 1;32                 if( i == m )33                 {34                     bFindPath = true;35                     q.clear();36                     break;37                 }38                 else 39                     q.push_back(i);40             } 41         }42     } 43             44     if (!bFindPath)45         return 0;46     int nMinFlow = 999999999;47     v = m;  //寻找源到汇路径上容量最小的边，其容量就是此次增 加的总流量48     while( Prev[v] )49     {   50         nMinFlow = min( nMinFlow,G[Prev[v]][v]); 51         v = Prev[v];52     } 53     //沿此路径添加反向边，同时修改路径上每条边的容量54     v = m; 55     while( Prev[v] )56     {  57         G[Prev[v]][v] -= nMinFlow;58         G[v][Prev[v]] += nMinFlow; 59         v = Prev[v];60     } 61     return nMinFlow;62 } 63             64 int main() 65 {66     while (cin >> n >> m) 67     {   68         //m是顶点数目，顶点编号从1开始69         int i,j,k;70         int s,e,c;71         memset( G,0,sizeof(G));72         for( i = 0;i < n;i ++ )73         {    74             cin >> s >> e >> c;  75             G[s][e] += c; //两点之间可能有多条边76         }   77         int MaxFlow = 0; 78         int aug; 79         while( aug = Augment() )80             MaxFlow += aug;  81         cout << MaxFlow << endl; 82     }  83     return 0; 84 }