|
|
back to boardWA1 ? Why i'm getting WA#1? #include<bits/stdc++.h> using namespace std; int capacities[2002][2002]; int flowPassed[2002][2002]; vector<int> graph[2002]; int parentsList[2002]; int currentPathCapacity[2002]; int bfs(int startNode, int endNode) { memset(parentsList, -1, sizeof(parentsList)); memset(currentPathCapacity, 0, sizeof(currentPathCapacity)); queue<int> q; q.push(startNode); parentsList[startNode] = -2; currentPathCapacity[startNode] = 999; while(!q.empty()) { int currentNode = q.front(); q.pop(); for(int i=0; i<graph[currentNode].size(); i++) { int to = graph[currentNode][i]; if(parentsList[to] == -1) { if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0) { parentsList[to] = currentNode; currentPathCapacity[to] = min(currentPathCapacity[currentNode], capacities[currentNode][to] - flowPassed[currentNode][to]); if(to == endNode) { return currentPathCapacity[endNode]; } q.push(to); } } } } return 0; } int edmondsKarp(int startNode, int endNode) { int maxFlow = 0; while(true) { int flow = bfs(startNode, endNode); if (flow == 0) { break; } maxFlow += flow; int currentNode = endNode; while(currentNode != startNode) { int previousNode = parentsList[currentNode]; flowPassed[previousNode][currentNode] += flow; flowPassed[currentNode][previousNode] -= flow; currentNode = previousNode; } } return maxFlow; } int main() { long int m,n,k,x; cin>>m>>n>>k; x=m+n; for(int i=0;i<k;i++) { int a,b; cin>>a>>b; graph[a].push_back(m+b); graph[m+b].push_back(a); capacities[a][m+b]=1; } for(int i=0;i<m;i++) {graph[0].push_back(i+1);capacities[0][i+1]=1;} for(int i=0;i<n;i++) {graph[m+i+1].push_back(x+1);capacities[m+i+1][x+1]=1;} int y=edmondsKarp(0,x+1); int p=(m-y+1)/2; p=p+(n-y+1)/2; cout<<(y+p)<<endl; } |
|
|