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
| const int N = 3000,M = 10000;
int h[N],ne[M],e[M],w[M],idx;
int win[N][N];
int n,m,S,T;
void add(int a,int b,int c){
w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx++;
w[idx] = 0,e[idx] = a,ne[idx] = h[b],h[b] = idx++;
}
namespace Dinic{
int q[N],d[N],cur[N];
bool bfs(){
int hh = 0,tt = -1;
memset(d,-1,sizeof(d));
d[S] = 0,cur[S] = h[S];
q[++tt] = S;
while(hh<=tt){
int u = q[hh++];
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(d[v]==-1&&w[k]){
d[v] = d[u]+1;
cur[v] = h[v];
if(v==T)
return true;
q[++tt] = v;
}
}
}
return false;
}
int find(int u,int lim){
if(u==T)
return lim;
int flow = 0;
for(int k=cur[u];~k&&flow<lim;k=ne[k]){
cur[u] = k;
int v = e[k];
if(d[v]==d[u]+1&&w[k]){
int t = find(v,min(w[k],lim-flow));
if(!t)
d[v] = -1;
w[k] -= t;
w[k^1] += t;
flow += t;
}
}
return flow;
}
int dinic(){
int r = 0,flow;
while(bfs())
if((flow=find(S,1e9)))
r += flow;
return r;
}
}
signed main(){
n = in(),m = in();
for(int k=1;k<=m;k++){
int a = in(),b = in();
win[a][b] = 1;
win[b][a] = 2;
}
S = 0,T = n+n*(n-1)/2+1;
for(int k=1;k<=n;k++){
memset(h,-1,sizeof(h));
idx = 0;
int cnt = n,wnt = 0;
for(int j=1;j<=n;j++)
for(int i=j+1;i<=n;i++){
add(S,++cnt,1);
if(win[i][j]){
if(win[j][i]==1){
if(j==k)
wnt++;
add(S,j,1);
}
else{
if(i==k)
wnt++;
add(S,i,1);
}
}
else{
if(j==k||i==k){
add(cnt,k,1);
wnt++;
}
else{
add(cnt,j,1);
add(cnt,i,1);
}
}
}
for(int j=1;j<=n;j++)
if(j==k)
add(j,T,wnt);
else
add(j,T,wnt-1);
if(Dinic::dinic()==n*(n-1)/2)
out(k,' ');
}
return 0;
}
|