Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <vector>
- #include <queue>
- #define INF 9999999
- using namespace std;
- int n;
- vector<vector<int>> capacity;
- vector<vector<int>> adj;
- int bfs(int s, int t, vector<int>& parent) {
- fill(parent.begin(), parent.end(), -1);
- parent[s] = -2;
- queue<pair<int, int>> q;
- q.push({s, INF});
- while (!q.empty()) {
- int cur = q.front().first;
- int flow = q.front().second;
- q.pop();
- for (int next : adj[cur]) {
- if (parent[next] == -1 && capacity[cur][next]) {
- parent[next] = cur;
- int new_flow = min(flow, capacity[cur][next]);
- if (next == t)
- return new_flow;
- q.push({next, new_flow});
- }
- }
- }
- return 0;
- }
- int maxflow(int s, int t) {
- int flow = 0;
- vector<int> parent(n+3);
- int new_flow;
- while (new_flow = bfs(s, t, parent)) {
- flow += new_flow;
- int cur = t;
- while (cur != s) {
- int prev = parent[cur];
- capacity[prev][cur] -= new_flow;
- capacity[cur][prev] += new_flow;
- cur = prev;
- }
- }
- return flow;
- }
- int main()
- {
- int m;
- scanf("%d%d",&n,&m);
- while (n != 0 || m != 0)
- {
- adj.resize(n+3);
- capacity = vector< vector<int> > (n+3, vector<int> (n+3, 0));
- int a, b, v;
- for(int i = 1; i <= n; i++)
- {
- scanf("%d", &v);
- if(v == 0)
- {
- adj[0].push_back(i);
- capacity[0][i] = 1;
- }
- else if(v == 1)
- {
- adj[i].push_back(n+1);
- capacity[i][n+1] = 1;
- }
- }
- for(int i = 0; i < m; i++)
- {
- scanf("%d%d", &a, &b);
- adj[a].push_back(b);
- capacity[a][b] = 1;
- adj[b].push_back(a);
- capacity[b][a] = 1;
- }
- int corte = maxflow(0,n+1);
- printf("%d\n", corte);
- adj.clear();
- scanf("%d%d",&n,&m);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement