题目传送门：http://acm.timus.ru/problem.aspx?space=1&num=1099
离线版题目：http://paste.ubuntu.com/19164744/
一般图匹配的板题
然而抄范大神的代码抄错了，调了一个下午QAQ
详细情况见之后的博文吧，会单独写一篇算法笔记的
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1000000;
int n,match[MAXN],fa[MAXN],que[MAXN],fro,bak;
int next[MAXN],mark[MAXN],vis[MAXN];
int T,nxt[MAXN],head[MAXN],to[MAXN];
inline int find(int w){
int f = fa[w], tmp;
while (f != fa[f]) f = fa[f];
while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
return f;
}
inline void merge(int a, int b){
int f1 = find(a), f2 = find(b);
if (f1 != f2) fa[f1] = f2;
}
inline int LCA(int x, int y){
static int t = 0; t++;
while (true){
if (x) {
x = find(x);
if (vis[x] == t) return x;
else {
vis[x] = t;
x = next[match[x]];
}
} swap(x, y);
}
}
inline void gather(int a, int p){
while (a != p){
int b = match[a], c = next[b];
if (find(c) != p) next = b;
if (mark[b] == 2) mark[que[++fro]=b] = 1;
if (mark == 2) mark[que[++fro]=c] = 1;
merge(a, b); merge(b, c);
a = c;
}
}
inline void Augment(int s){
for (int i=1;i<=n;i++) next[i]=mark[i]=vis[i]=0, fa[i]=i;
mark[s] = 1; que[fro=bak=1] = s;
while (bak <= fro) {
int w = que[bak++];
for (int i=head[w];i;i=nxt[i]){
if (match[w] == to[i]) continue;
else if (find(to[i]) == find(w)) continue;
else if (mark[to[i]] == 2) continue;
else if (mark[to[i]] == 1) {
int lca = LCA(w, to[i]);
if (find(w) != lca) next[w] = to[i];
if (find(to[i]) != lca) next[to[i]] = w;
gather(w, lca);
gather(to[i], lca);
} else if (!match[to[i]]) {
next[to[i]] = w;
for (int u=to[i]; u; ) {
int v = next[u];
int fv = match[v];
match[v] = u; match[u] = v;
u = fv;
}
return;
} else {
next[to[i]] = w;
mark[que[++fro] = match[to[i]]] = 1;
mark[to[i]] = 2;
}
}
}
}
inline void AddEdge(int a, int b){
to[++T] = b; nxt[T] = head[a]; head[a] = T;
to[++T] = a; nxt[T] = head[b]; head[b] = T;
}
int main(){
scanf("%d",&n); int a,b;
while (~scanf("%d%d",&a,&b)) AddEdge(a, b);
for (int i=1;i<=n;i++) if (!match[i]) Augment(i);
int vout = 0;
for (int i=1;i<=n;i++) if (match[i]) vout++;
printf("%d\n",vout);
for (int i=1;i<=n;i++) if (match[i] > i) printf("%d %d\n",i,match[i]);
return 0;
}
另外，此题有坑QAQ
边数巨多，TM还不告诉你是RE，给你说的是TLEQAQ
哇塞，居然是沙发？留个名
Nice blog! Is your theme custom made or did you download it
from somewhere? A theme like yours with a few simple
adjustements would really make my blog jump out. Please
let me know where you got your design. Thanks
Just want to say your article is as amazing. The clarity for your put up is just cool
and i could suppose you are a professional on this subject.
Well along with your permission let me to clutch
your feed to keep updated with forthcoming post.
Thank you 1,000,000 and please continue the enjoyable work.
This paragraph provides clear idea in favor of
the new users of blogging, that genuinely how to do blogging.
I’ve been surfing online more than 3 hours
today, yet I never found any interesting article like yours.
It’s pretty worth enough for me. Personally, if all webmasters and bloggers made good content as you did, the net will be
much more useful than ever before.
What i do not realize is in reality how you are now not really much more smartly-favored than you might be
now. You are so intelligent. You know therefore considerably in relation to this matter, produced me
personally consider it from numerous varied angles.
Its like women and men don’t seem to be fascinated until it is one thing to do with
Woman gaga! Your personal stuffs excellent. Always
care for it up!
My programmer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using Movable-type on several websites for
about a year and am anxious about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can import all my wordpress posts into it?
Any help would be greatly appreciated!
I have to thank you for the efforts you have put in writing
this website. I really hope to see the same high-grade blog posts by you in the future as well.
In fact, your creative writing abilities has encouraged
me to get my own site now 😉
Right now it appears like Drupal is the top blogging platform available right now.
(from what I’ve read) Is that what you are using on your blog?
Great article. I will be dealing with a few of these issues
as well..
It’s an awesome paragraph in favor of all the online visitors; they will obtain benefit from it I am sure.
Great beat ! I would like to apprentice while you amend your site, how can i subscribe for
a weblog website? The account helped me a appropriate deal.
I had been a little bit familiar of this your broadcast offered brilliant transparent concept
Hi there, I read your blogs regularly. Your story-telling style is awesome, keep it up!
Its such as you learn my thoughts! You appear to know so much about this,
like you wrote the e-book in it or something.
I feel that you just could do with some percent to force the message home a little bit, however other than that,
that is wonderful blog. An excellent read. I’ll certainly be
back.
Good day! This is my first visit to your blog!
We are a collection of volunteers and starting a new initiative in a community in the same niche.
Your blog provided us beneficial information to work on. You have done a marvellous job!
Hi there everyone, it’s my first pay a quick visit at this
site, and post is in fact fruitful designed for me, keep up
posting these types of articles or reviews.
What i do not realize is in fact how you are now not really a lot more neatly-preferred than you might be now. You are very intelligent. You understand therefore significantly on the subject of this subject, produced me for my part consider it from numerous numerous angles. Its like men and women don’t seem to be involved except it is something to do with Lady gaga! Your personal stuffs excellent. Always care for it up!
Wonderful blog! Do you have any tips for
aspiring writers? I’m planning to start my own website soon but I’m a little
lost on everything. Would you advise starting with a free platform like WordPress
or go for a paid option? There are so many choices out there that I’m totally overwhelmed ..
Any tips? Many thanks!
We’re a group of volunteers and starting a brand new scheme in our
community. Your site provided us with valuable info to work on. You have done a formidable activity and our whole group shall be grateful to you.
Good article! We will be linking to this great content
on our website. Keep up the great writing.
Have you ever thought about publishing an ebook or guest authoring on other sites?
I have a blog centered on the same subjects you discuss and would
really like to have you share some stories/information.
I know my subscribers would value your work. If you are even remotely interested, feel
free to shoot me an email.
Actually no matter if someone doesn’t know afterward its up to other viewers that they will assist, so
here it occurs.
What’s up, for all time i used to check web site posts here in the early hours in the break of day, as i like to find out more and more.
Link exchange is nothing else except it is simply placing the
other person’s web site link on your page at suitable place
and other person will also do similar in favor of you.
I have to thank you for the efforts you’ve put in penning this
site. I’m hoping to check out the same high-grade blog posts
by you later on as well. In fact, your creative writing abilities has inspired me to get my own site now 😉
I was able to find good info from your content.
Hi there! This is my first visit to your blog!
We are a collection of volunteers and starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You
have done a marvellous job!
I think this internet site holds some real fantastic info for everyone :D. “Time–our youth–it never really goes, does it It is all held in our minds.” by Helen Hoover Santmyer.