文档章节

【UOJ#80】二分图最大权匹配(KM)

o
 osc_1ee7cxmx
发布于 2018/08/06 21:11
字数 330
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

##题面 UOJ ##题解 模板qaq

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 850
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,nl,nr,m,a[MAX][MAX];
int slack[MAX],sl[MAX],sr[MAX],pre[MAX],match[MAX];
bool vis[MAX];
ll ans;
void bfs(int S)
{
	memset(slack,127,sizeof(slack));
	memset(vis,0,sizeof(vis));
	memset(pre,0,sizeof(pre));
	int u,nt,d,nw;
	match[u=0]=S;
	do
	{
		nw=match[u];d=slack[0];vis[u]=true;
		for(int v=1;v<=n;++v)
			if(!vis[v])
			{
				if(sl[nw]+sr[v]-a[nw][v]<slack[v])
					slack[v]=sl[nw]+sr[v]-a[nw][v],pre[v]=u;
				if(d>slack[v])d=slack[v],nt=v;
			}
		for(int i=0;i<=n;++i)
			if(vis[i])sl[match[i]]-=d,sr[i]+=d;
			else slack[i]-=d;
		u=nt;
	}while(match[u]);
	while(u)match[u]=match[pre[u]],u=pre[u];
}
int main()
{
	nl=read();nr=read();m=read();n=max(nl,nr)<<1;
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		a[u][v]=max(a[u][v],read());
		sl[u]=max(sl[u],a[u][v]);
	}
	for(int i=1;i<=nl;++i)bfs(i);
	for(int i=1;i<=n;++i)ans+=sl[i]+sr[i];
	printf("%lld\n",ans);memset(pre,0,sizeof(pre));
	for(int i=1;i<=n;++i)pre[match[i]]=i;
	for(int i=1;i<=nl;++i)printf("%d ",a[i][pre[i]]?pre[i]:0);
	return 0;
	
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Mysql主从同步

1主从同步 1.1Master 1.1.1配置--编辑 my.cnf #编辑 mysql 的 /etc/my.cnf 配置文件vi /etc/my.cnf#添加如下配置server-id=1 #设置服务 IDlog_bin=mysql-bin #启动 binlog...

风雪满弓刀
17分钟前
0
0
修复 `管道菜单“/usr/bin/obamenu”的输出无效 `错误

修复 管道菜单“/usr/bin/obamenu”的输出无效 错误 英文提示应该是 invalid output from pipe-menu "obamenu" 使用 openbox 菜单时碰到了这个错误,上网搜了一下,找到了原因,也就想到了解...

tankb52
31分钟前
13
0
2020最新微信域名防封技术 微信域名防封系统是如何操作的

相信很多朋友在运营自己产品的网站或者是推广链接的时候,经常会发现运行的好好的网站链接突然就被封了,有一部分因为可能是网站的内容触犯了微信的规则,但是还有很大的一部分被同行恶意投诉...

戚馨逸
54分钟前
11
0
mysql 为什么 SQL 语句不要过多的 join?

第一部分 Linux上查看内存的使用情况该用什么命令 free -mh 可以看到内存或者缓存情况 total 总内存 used 已用内存 free 空闲内存 buff/cache 已使用的缓存 avaiable 可用内存 怎么清理已使...

edison_kwok
54分钟前
17
0
芒果TV的金融野心从未停止

来源|WEMONEY研究室 作者|林小林 芒果TV是真的会讲故事,《乘风破浪的姐姐》不仅是生活的故事更是资本的故事,30位姐姐让一款节目累计播放量飙升10亿,同时让背后的上市公司芒果超媒市值站...

镭射财经
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部