6、8、10、11WA了,刚建号下不了数据,也查不出来哪里有问题,求助?
#include <iostream>
using namespace std;
struct edge{
int u;
int v;
};
int flow(int**,int);
int bottleneck(edge *P, int len, int **f, int **Graph){
for(int i = 0; i <= len; i++){
int u = P[i].u;
int v = P[i].v;
if(Graph[u][v] == f[u][v]){
return 0;
}
}
return 1;
}
void augment(int **f, edge *P, int len, int** Graph){
int b = bottleneck(P,len,f,Graph);
for(int i = 0; i <= len; i++){
int u = P[i].u;
int v = P[i].v;
if(Graph[u][v] > f[u][v]){
f[u][v] += b;
}
else{
f[v][u] -= b;
}
}
}
void Graph0(int **f, int** Graph, int n, int** Graphf){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(f[i][j] > 0){
Graphf[i][j] = 0;
Graphf[j][i] = 1;
}
else{
Graphf[i][j] = Graph[i][j];
}
}
}
}
int dfs(int u, int **Graph, int n, bool* visited, edge *P, int len){
visited[u] = true;
for(int v = n-1; v >= 0; v--){
if(Graph[u][v] > 0 && !visited[v]){
if(v==n-1){
P[len].u=u;
P[len].v=v;
return len;
}
int next = dfs(v,Graph,n,visited,P,len+1);
if(next){
P[len].u=u;
P[len].v=v;
return next;
}
}
}
return 0;
}
int findP(int** Graph, int n, edge* P){
bool* visited = new bool[n];
for(int i = 0; i < n; i++){
visited[i] = false;
}
int found = dfs(0,Graph,n,visited,P,0);
delete[] visited;
return found;
}
void showP(edge* P, int len){
for(int i = 0; i <= len; i++){
cout<<P[i].u<<','<<P[i].v<<endl;
}
}
int** Max_Flow(int** Graph, int n){
int **Graphf = new int*[n];
int** f = new int*[n];
for(int i = 0; i < n; i++){
Graphf[i] = new int[n];
f[i] = new int[n];
}
edge *P = new edge[n-1];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
f[i][j] = 0;
}
}
Graph0(f,Graph,n,Graphf);
int len = findP(Graphf,n,P);
while(len){
augment(f,P,len,Graph);
Graph0(f,Graph,n,Graphf);
len = findP(Graphf,n,P);
}
for(int i = 0; i < n; i++){
delete[] Graphf[i];
}
delete[] Graphf;
delete[] P;
return f;
}
int flow(int** f,int m){
int maxflow = 0;
for(int i = 1; i <= m; i++){
if(f[0][i] > 0){
maxflow++;
}
}
return maxflow;
}
int main(){
int n, m;
cin>>m>>n;
int N = n+2;
int** Graph = new int*[N];
for(int i = 0; i < N; i++){
Graph[i] = new int[N];
for(int j = 0; j < N; j++){
Graph[i][j] = 0;
}
}
int u,v;
while(1){
cin>>u>>v;
if(u == -1 || v == -1){
break;
}
Graph[u][v] = 1;
Graph[0][u] = 1;
Graph[v][n+1] = 1;
}
int** f = Max_Flow(Graph,N);
int maxflow = 0;
for(int i = 1; i <= m; i++){
if(f[0][i] > 0){
maxflow++;
}
}
cout<<maxflow<<endl;
for(int i = 1; i <= m; i++){
if(f[0][i] > 0){
cout<<i<<' ';
for(int j = m+1; j <= n; j++){
if(f[i][j] > 0){
cout<<j<<endl;
break;
}
}
}
}
for(int i = 0; i < n; i++){
delete[] Graph[i];
delete[] f[i];
}
delete[] Graph;
delete[] f;
}