1 #include<iostream>  2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7  8 int n, m, flow; 9 int vis[205];10 //路径记录11 int pre[205];12 //邻接表13 int G[205][205];14 15 void Maxflow()16 {17     for (;;)18     {19         memset(vis, 0, sizeof(vis));20         memset(pre, 0, sizeof(pre));21         queue<int> q;22         q.push(1);23         vis[1] = 1;24         while (!q.empty())25         {26             int x = q.front();27             q.pop();28             //到达终点29             if (x == n)  break;30             for (int i = 1; i <= n; i++)31             {32                 if (!vis[i] && G[x][i] > 0)33                 {34                     vis[i] = 1;35                     q.push(i);36                     //记录好路径37                     pre[i] = x;38                 }39             }40         }41         //没有找到增广路42         if (!vis[n])  break;43         int _min = 1000000;44         for (int i = n; i != 1; i = pre[i])45             _min = min(_min, G[pre[i]][i]);46         for (int i = n; i != 1; i = pre[i])47         {48             G[i][pre[i]] += _min;49             G[pre[i]][i] -= _min;50         }51         flow += _min;52     }53     return;54 }55 56 int main()57 {58     //freopen("D:\\txt.txt", "r", stdin);59     int T;60     int u, v, w;61     cin >> T;62     for (int kase = 1; kase <= T; kase++)63     {64         cin >> n >> m;65         memset(G, 0, sizeof(G));66         for (int i = 0; i < m; i++)67         {68             cin >> u >> v >> w;69             G[u][v] += w;70         }71         flow = 0;72         Maxflow();73         cout << "Case " << kase << ": " << flow << endl;74     }75 }