题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=728
这个玩意，我们可以参考：https://oi.men.ci/cogs-728/
也可以参考：https://www.byvoid.com/blog/lpf24-3
这题我觉得可以想成是点的入读与出度之间相互匹配
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 10000;
const int M = 100000;
const int INF = 1000000;
int head[N],cur[N],dis[N],nxt[M],to[M],flow[M];
int vout,n,m,S,T,vis[N];
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void Add_Edge(int u, int v, int f){
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
}
return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
if (!f) break;
}
return ret;
}
}
inline int Dinic(){
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
}
return ret;
}
void print(int w) {
vis[w] = 1; printf("%d ",w);
for (int i=head[w];i;i=nxt[i]) if (!flow[i] && !vis[to[i]])
{print(to[i]>n?to[i]-n:to[i]); break;}
}
int main(){
freopen("path3.in","r",stdin);
freopen("path3.out","w",stdout);
vout = n = read(); m = read(); S = 0; T = N-1; vis[S] = vis[T] = 1;
for (int i=1,u,v;i<=m;i++) u = read(), v = read(), Add_Edge(u,v+n,1);
for (int i=1;i<=n;i++) Add_Edge(S,i,1), Add_Edge(i+n,T,1);
vout -= Dinic();
for (int i=1,w;i<=n;i++) if (!vis[i])
print(i), putchar('\n');
printf("%d\n",vout);
return 0;
}
值得一提的是，这题的SPJ居然对于文末回车敏感 (╯‵□′)╯︵┻━┻
害的老子调了一个小时 QAQ
I believe that is among the such a lot vital info for me.
And i am satisfied reading your article. However wanna remark on some basic issues, The
web site taste is great, the articles is really nice :
D. Excellent job, cheers
Hi there would you mind stating which blog platform you’re
working with? I’m looking to start my own blog
soon but I’m having a tough time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs
and I’m looking for something completely unique.
P.S Sorry for getting off-topic but I had to ask!
Pretty nice post. I just stumbled upon your weblog and
wished to say that I have truly enjoyed surfing around your blog
posts. After all I’ll be subscribing to your rss feed and I hope you write again very soon!
Oh my goodness! Impressive article dude! Thanks, However I am experiencing issues with your
RSS. I don’t know the reason why I cannot join it. Is there anybody else getting identical RSS problems?
Anyone that knows the answer can you kindly
respond? Thanx!!
I really like reading through a post that will make men and women think.
Also, many thanks for permitting me to comment!
An impressive share! I’ve just forwarded this onto a friend who
has been conducting a little homework on this. And he actually ordered me breakfast due to
the fact that I discovered it for him… lol. So allow me to reword this….
Thanks for the meal!! But yeah, thanks for spending time to
discuss this subject here on your site.
Generally I don’t read post on blogs, however I wish to say that
this write-up very pressured me to take a look
at and do it! Your writing style has been amazed me. Thank you, very great article.
Your style is really unique compared to other folks I have read stuff from.
Thank you for posting when you’ve got the opportunity,
Guess I will just book mark this web site.
Woah! I’m really loving the template/theme of this website.
It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between usability and visual appeal.
I must say that you’ve done a excellent job with this.
In addition, the blog loads very quick for me on Chrome. Outstanding Blog!
I was excited to find this great site. I need to to thank
you for ones time just for this wonderful read!! I definitely loved every part
of it and I have you saved to fav to see new stuff on your
website.
I’m gone to say to my little brother, that he
should also pay a visit this weblog on regular basis to get updated from hottest news update.
Thank you, I’ve just been looking for information about this subject for ages and yours is the greatest I have came
upon till now. But, what concerning the bottom line?
Are you certain in regards to the source?
Remarkable! Its really amazing article, I have got much clear idea concerning from this article.
A motivating discussion is worth comment. I think that you need to
write more on this issue, it may not be a taboo matter but generally folks don’t talk about these topics.
To the next! Cheers!!
Wow! This blog looks exactly like my old one! It’s on a totally different topic but it has pretty
much the same layout and design. Outstanding choice of colors!
Hiya, I am really glad I have found this info. Nowadays bloggers publish only about gossips and internet and this is actually irritating. A good web site with interesting content, this is what I need. Thanks for keeping this web site, I will be visiting it. Do you do newsletters? Can not find it.
We’re a gaggle of volunteers and opening a brand new scheme in our community.
Your website offered us with valuable information to
work on. You’ve done a formidable task and our whole
group will probably be grateful to you.
Hey! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing several weeks of hard work due to no back up.
Do you have any methods to protect against hackers?
There’s certainly a lot to know about this issue.
I really like all the points you have made.
Hi, i feel that i saw you visited my weblog thus i got here to go back the
want?.I’m attempting to in finding issues to enhance my site!I
guess its adequate to use a few of your ideas!!
Hello everybody, here every one is sharing these familiarity,
therefore it’s good to read this weblog, and I used to pay a quick visit
this webpage everyday.
Why viewers still make use of to read news papers when in this technological world all is existing
on web?
In fact when someone doesn’t be aware of then its up to other people that they will help, so here it occurs.
Currently it sounds like Expression Engine
is the best blogging platform out there right now.
(from what I’ve read) Is that what you’re using on your blog?
My brother suggested I may like this web site. He was entirely right. This post actually made my day. You can not believe simply how so much time I had spent for this information! Thanks!
Thank you for your article post.Really thank you! Fantastic.