【UOJ 80】二分图最大权匹配

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

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

本来想拿MCMF来水一发，结果T到死，不想回忆KMQAQ
管他的，先放在这里不管了，今天的主要任务是带花树！

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 600000;
const int INF = 100000000;

int n1,n2,m,s,t; LL vout;
int T=1,to[MAXN],nxt[MAXN],head[MAXN],cap[MAXN],flow[MAXN],cost[MAXN];
int dis[MAXN],que[MAXN],fro,bak,inq[MAXN],from[MAXN],scr[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, int COST){
	to[++T] = b; from[T] = a; nxt[T] = head[a]; head[a] = T; cap[T] = CAP; cost[T] = COST;
	to[++T] = a; from[T] = b; nxt[T] = head[b]; head[b] = T; cap[T] = 0; cost[T] = -COST;
}

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

inline void MCMF(){
	while (SPFA()){
		int w = t; while (w != s) 
			flow[scr[w]] += 1, flow[scr[w]^1] -= 1, 
			vout += cost[scr[w]], w = from[scr[w]]; 
	}
}

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

15 thoughts to “【UOJ 80】二分图最大权匹配”

  1. 847370 632332Right after study several of the content material within your internet website now, and i also truly much like your way of blogging. I bookmarked it to my bookmark internet site list and are checking back soon. Pls take a look at my internet page also and inform me how you feel. 708673

    Reply

  3. 166780 686699I see your point, and I completely appreciate your article. For what its worth I will tell all my friends about it, quite resourceful. Later. 501410

    Reply

  4. 765510 742549Im so happy to read this. This is the type of manual that needs to be given and not the accidental misinformation thats at the other blogs. Appreciate your sharing this greatest doc. 794070

    Reply

  7. 26344 563328Hoping to go into business venture world-wide-web Indicates revealing your products or services furthermore companies not only to ladies locally, but nevertheless , to numerous prospective clients in which are online in most cases. e-wallet 305703

    Reply

  8. 423449 56986We offer you with a table of all of the emoticons that can be used on this application, and the meaning of each symbol. Though it might take some initial effort on your part, the skills garnered from regular and strategic use of social media will create a strong foundation to grow your business on ALL levels. 884798

    Reply

  11. 225418 97257I like the valuable data you give inside your articles. Ill bookmark your weblog and check once more here regularly. Im quite certain I will learn a lot of new stuff correct here! Good luck for the next! 902454

    Reply

Leave a Reply

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