1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#define MAX_V 1000
using namespace std;
const int INF = (unsigned int)(-1)>>1;
struct edge {
int to,cap,rev;
};
vector<edge> G[MAX_V]; //图的邻接表表示
int level[MAX_V]; //结点到源点的距离标号
int iter[MAX_V]; //当前弧，在其之前的边已经没有用了
//向图中增加一条从from到to的容量为cap(剩余流量)的边
void add_edge(int from,int to,int cap) {
G[from].push_back((edge) {
to,cap,G[to].size()
});
G[to].push_back((edge) {
from,0,G[from].size()-1
});
}
//通过BFS计算从源点出发的距离标号
void bfs(int s) {
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty()) {
int v = que.front();
que.pop();
for(int i=0; i<G[v].size(); i++) {
edge &e = G[v][i];
if(e.cap > 0 && level[e.to]<0) {
level[e.to] = level[v] +1;
que.push(e.to);
}
}
}
}
//通过DFS寻找增广路
int dfs(int v,int t,int f) {
if(v == t)return f;
for(int &i=iter[v]; i<G[v].size(); i++) {
edge &e = G[v][i];
if(e.cap > 0 && level[v] < level[e.to]) {
int d =dfs(e.to,t,min(f,e.cap));
if(d>0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
//求解从s到t的最大流
int max_flow(int s, int t) {
int flow = 0;
for(;;) {
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f= dfs(s,t,INF))>0) {
flow += f;
}
}
}
int n,m;
int main()
{
cin>>m>>n;
int s=0,t=n+1;
int a,b;
for(int i=1;i<=m;i++)
{
add_edge(s,i,1);
}
for(int i=m+1;i<=n;i++)
{
add_edge(i,t,1);
}
while(cin>>a>>b)
{
if(a==-1&&b==-1)break;
add_edge(a,b,1);
}
int ans = max_flow(s,t);
cout<<ans<<endl;
if(ans==0)cout<<"No Solution!";
else{
for(int i=1;i<=m;++i){
for(int j=0;j<G[i].size();++j){
edge &e = G[i][j];
if(e.cap==0&&e.to>m&&e.to<=n){
cout<<i<<" "<<e.to<<endl;
break;
}
}
}
}
return 0;
}
|