【UOJ 78】二分图最大匹配

Qizy 二分图匹配, 图论, 网络流, 解题报告

题目传送门：http://uoj.ac/problem/78
离线版题目：http://paste.ubuntu.com/19130171/

今天来搞一搞图论，先来一发二分图。
Dinic此题的时间还是不错的，能踩Dinic的，都只有二分图专门的算法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 5000000+9;
const int INF = 10000000;

int n1,n2,m,s,t,vout;
int T=1,to[MAXN],nxt[MAXN],head[MAXN];
int dis[MAXN],que[MAXN],fro,bak;
int cap[MAXN],flow[MAXN],cur[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void AddEdge(int a, int b, int CAP){
	to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = CAP;
	to[++T] = a; nxt[T] = head[b]; head[b] = T; cap[T] = 0;
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	que[fro=bak=1] = s; dis[s] = 0;
	
	while (bak <= fro) {
		int w = que[bak++];
		for (int i=head[w];i;i=nxt[i])
			if (flow[i] < cap[i] && dis[to[i]] == -1)
				dis[to[i]] = dis[w] + 1, que[++fro] = to[i];
	}
	
	return dis[t] != -1;
}

int MaxFlow(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] < cap[i] && dis[to[i]] == dis[w] + 1){
				int tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
				flow[i] += tmp; flow[i^1] -= tmp;
				ret += tmp; if (ret == f) return ret; 
			}
		}
		return ret;
	}
}

inline void Dinic(){
	while (BFS()){
		for (int i=0;i<=t;i++) cur[i] = head[i];
		vout += MaxFlow(s, INF);
	}
}

int main(){
	n1=read(); n2=read(); m=read();
	s = 0; t = n1 + n2 + 1;
	for (int i=1,a,b;i<=m;i++)
		a = read(), b = read(),
		AddEdge(a,n1+b,1);
	for (int i=1;i<=n1;i++) AddEdge(s,i,1);
	for (int i=n1+1;i<=n1+n2;i++) AddEdge(i,t,1);
	Dinic();
	printf("%d\n",vout);
	for (int w=1;w<=n1;w++){
		vout = 0;
		for (int i=head[w];i;i=nxt[i])
			if (flow[i] && to[i] > n1) {
				vout = to[i]-n1; break;
			}
		printf("%d\n",vout);
	}
	return 0;
}

211 thoughts to “【UOJ 78】二分图最大匹配”

  20. Hey There. I found your blog using msn. This is a really well written article.
    I’ll be sure to bookmark it and come back to read
    more of your useful info. Thanks for the post. I will definitely
    return.

    Reply

  27. I will immediately seize your rss as I can not find your email subscription link or newsletter service.
    Do you have any? Please permit me recognise in order that I could subscribe.

    Thanks.

    Reply

  43. My brother suggested I may like this website.
    He was totally right. This submit actually made my day. You can not believe just how a lot time I had spent for this info!

    Thank you!

    Reply

  51. It’s a pity you don’t have a donate button! I’d most
    certainly donate to this fantastic blog! I guess for now i’ll settle for
    bookmarking and adding your RSS feed to my Google account.
    I look forward to brand new updates and will share this blog with my Facebook group.
    Talk soon!

    Reply

  59. Howdy! Someone in my Facebook group shared this website with
    us so I came to give it a look. I’m definitely loving the information. I’m book-marking and will be
    tweeting this to my followers! Terrific blog and wonderful style and design.

    Reply

  68. We’re a gaggle of volunteers and opening a new scheme in our community.
    Your site offered us with useful info to work on. You’ve done an impressive job and our
    whole group might be grateful to you.

    Reply

  71. I am often to blogging and i really appreciate your content. The article has really peaks my interest. I am going to bookmark your site and keep checking for new information.

    Reply

  76. Today, I went to the beach with my children. I found a
    sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the
    shell to her ear and screamed. There was a hermit crab
    inside and it pinched her ear. She never wants to go back!
    LoL I know this is completely off topic but I
    had to tell someone!

    Reply

  113. Thanks for a marvelous posting! I certainly enjoyed reading it, you may be a great author.

    I will be sure to bookmark your blog and may come back
    sometime soon. I want to encourage yourself to continue
    your great writing, have a nice afternoon!

    Reply

  126. What’s up, this weekend is pleasant in favor of me, as this point in time i am reading this
    impressive educational article here at my house.

    Reply

  168. Nice post. I learn one thing more challenging on different blogs everyday. It can at all times be stimulating to learn content material from different writers and apply slightly something from their store. I’d prefer to make use of some with the content on my weblog whether you don’t mind. Natually I’ll offer you a hyperlink in your web blog. Thanks for sharing.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *