luogu2756

这道题,本来是用匈牙利做的,不过看了这个输入,就想练习一下带花树

还是对这模板调了一下,不过好像还背不了

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
#define N 210
#include<vector>
vector<int>t[N];
int nn,n,u,v;
#include<queue>
queue<int>q;
int p[N],odd[N],vis[N],cnt,f[N],ans,pre[N];
int getf(int x)
{
return f[x]=f[x]==x?x:getf(f[x]);
}
int lca(int u,int v)
{
cnt++;
while(vis[u]!=cnt)
{
if(u)
{
u=getf(u);
if(vis[u]==cnt)
return u;
vis[u]=cnt;
if(p[u])
u=getf(pre[p[u]]);
else
u=0;
}
int k=u;
u=v;
v=k;
}
return u;
}//这里背下来了
void circle(int u,int v,int ff)
{
while(getf(u)!=ff)
{
pre[u]=v;
if(odd[p[u]]==1)
{
odd[p[u]]=0;
q.push(p[u]);
}
if(f[p[u]]==p[u])
f[p[u]]=ff;
if(f[u]==u)
f[u]=ff;
v=p[u];
u=pre[v];
}
}//这里还差一点
int flower(int x)
{
fr(i,1,n)
{
f[i]=i;
odd[i]=-1;
}
odd[x]=0;
while(!q.empty())q.pop();
q.push(x);
while(!q.empty())
{
int u=q.front();
q.pop();
fr(i,0,t[u].size()-1)
{
int v=t[u][i];
if(odd[v]==-1)
{
pre[v]=u;
odd[v]=1;//这个地方背错了一点
if(!p[v])
{
int th,las,now=v;
while(now)
{
th=pre[now];
las=p[th];
p[th]=now;
p[now]=th;
now=las;
}
return 1;
}
odd[p[v]]=0;
q.push(p[v]);
}
else
if(!odd[v]&&getf(u)!=getf(v))
{
int l=lca(u,v);
circle(u,v,l);
circle(v,u,l);
}//这里也背下来了
}
}
return 0;
}
int main()
{
nn=read();
n=read();
u=read();
v=read();
while(u!=-1&&v!=-1)
{
t[u].push_back(v);
t[v].push_back(u);
u=read();
v=read();
}
fr(i,1,nn)
if(!p[i])
ans+=flower(i);
if(!ans)
{
printf("No Solution!\n");
return 0;
}
printf("%d\n",ans);
fr(i,1,nn)
if(p[i])
printf("%d %d\n",i,p[i]);
return 0;
}