从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。
有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶，且结为配偶后幸福程度为 ww。
请问这个班级里幸福程度之和最大是多少？
输入格式
第一行三个正整数，nl,nr,mnl,nr,m。
接下来 mm 行，每行三个整数 v,u,wv,u,w 表示第 vv 个男生和第 uu 个女生愿意结为配偶，且幸福程度为 ww。保证 1≤v≤nl1≤v≤nl，1≤u≤nr1≤u≤nr，保证同一对 v,uv,u 不会出现两次。
输出格式
第一行一个整数，表示幸福程度之和的最大值。
接下来一行 nlnl 个整数，描述一组最优方案。第 vv 个整数表示 vv 号男生的配偶的编号。如果 vv 号男生没配偶请输出 00。
样例一
input
2 2 3
1 1 100
1 2 1
2 1 1
output
100
1 0
限制与约定
1≤nl,nr≤4001≤nl,nr≤400，1≤m≤1600001≤m≤160000，1≤w≤1091≤w≤109。
时间限制：1s1s
空间限制：256MB
二分图最大权匹配模板题 KM算法
KM算法略神奇的样子……
http://www.cnblogs.com/wenruo/p/5264235.html
↑感觉这里讲得挺清晰
KM算法求的是最大权完备匹配，为了解决两边点数不同的情况，需要虚拟一些点使得两边点数相等
↑但是这种DFS写法被无情卡掉
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const LL INF=1LL<<;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void write(LL x){
if(x>)write(x/);
putchar(x%+'');
return;
}
inline LL mini(LL a,LL b){return a<b?a:b;}
inline LL maxi(LL a,LL b){return a>b?a:b;}
int nL,nR,bl,br,m;
int visL[mxn],visR[mxn];
LL exL[mxn],exR[mxn];
int link[mxn];
LL slack[mxn];
int mp[mxn][mxn];
LL ans=;
int a[mxn];
int dtime=;
bool DFS(int u){
visL[u]=dtime;
for(int i=;i<=nR;i++){
if(visR[i]==dtime)continue;
LL d=exL[u]+exR[i]-mp[u][i];
if(!d){
visR[i]=dtime;
if(!link[i] || DFS(link[i])){
link[i]=u;
return ;
}
}
else slack[i]=min(slack[i],d);
}
return ;
}
void KM(){
// memset(link,0,sizeof link);
// memset(exR,0,sizeof exR);
for(int i=;i<=nL;i++){
exL[i]=;
for(int j=;j<=nR;j++){
exL[i]=maxi(exL[i],mp[i][j]);
}
}
for(int i=;i<=nL;i++){
// memset(slack,0x3f,sizeof slack);
for(int j=;j<=nR;j++)slack[j]=INF;
while(){//直到匹配成功为止
dtime++;
// memset(visL,0,sizeof visL);
// memset(visR,0,sizeof visR);
if(DFS(i))break;
LL d=INF;
for(int j=;j<=nR;j++){
if(visR[j]!=dtime)d=mini(d,slack[j]);
}
for(int j=;j<=nL;j++){
if(visL[j]==dtime)exL[j]-=d;
if(visR[j]==dtime)exR[j]+=d;
else slack[j]-=d;
}
}
}
ans=;
nL=bl;nR=br;
for(int i=;i<=nR;i++){
if(mp[link[i]][i]){
a[link[i]]=i;
ans+=mp[link[i]][i];
}
}
printf("%lld\n",ans);
for(int i=;i<=nL;i++){
write(a[i]);
putchar(' ');
}
printf("\n");
return;
}
int main(){
int i,j;
nL=read();
nR=read();
bl=nL;br=nR;
nL=max(nL,nR);
nR=nL;
m=read();
int u,v,w;
for(i=;i<=m;i++){
u=read();v=read();w=read();
mp[u][v]=w;
}
KM();
return ;
}
DFS TLE
于是在status里抄了个BFS的写法。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void write(LL x){
if(x>)write(x/);
putchar(x%+'');
return;
}
inline int mini(int a,int b){return a<b?a:b;}
inline int maxi(int a,int b){return a>b?a:b;}
int nL,nR,bl,br,m;
int visL[mxn],visR[mxn];
int exL[mxn],exR[mxn];
int link[mxn],pre[mxn],lx[mxn];
int slack[mxn];
int mp[mxn][mxn];
//
LL ans=;
int a[mxn];
int dtime=;
int q[mxn<<],hd,tl;
void Aug(int rt){
if(!rt)return;
link[rt]=pre[rt];
Aug(lx[pre[rt]]);
lx[pre[rt]]=rt;
return;
}
void BFS(int S){
int i,j,tmp;++dtime;
memset(slack,0x3f,sizeof slack);
hd=tl=;q[tl]=S;
while(){
while(hd<=tl){
int u=q[hd];++hd;
visL[u]=dtime;
for(int i=;i<=nR;i++){
if(visR[i]^dtime){
tmp=exL[u]+exR[i]-mp[u][i];
if(!tmp){
visR[i]=dtime;pre[i]=u;
if(!link[i]){
Aug(i);
return;
}
q[++tl]=link[i];
//
}
else if(tmp<slack[i])slack[i]=tmp,pre[i]=u;
}
}
}
tmp=INF;
for(i=;i<=nR;i++)if(visR[i]^dtime)tmp=mini(tmp,slack[i]);
for(i=;i<=nL;i++){
if(visL[i]==dtime)exL[i]-=tmp;
if(visR[i]==dtime)exR[i]+=tmp;
else slack[i]-=tmp;
}
for(i=;i<=nR;i++){
if(visR[i]^dtime && !slack[i]){
visR[i]=dtime;
if(!link[i]){
// link[i]=pre[i];
Aug(i);
return;
}
q[++tl]=link[i];
}
}
}
return;
}
void KM(){
for(int i=;i<=nL;i++){
exL[i]=;
for(int j=;j<=nR;j++)
exL[i]=max(exL[i],mp[i][j]);
}
for(int i=;i<=nL;i++) BFS(i);
ans=;
nL=bl;nR=br;
for(int i=;i<=nR;i++){
if(mp[link[i]][i]){
a[link[i]]=i;
ans+=mp[link[i]][i];
}
}
printf("%lld\n",ans);
for(int i=;i<=nL;i++){
write(a[i]);
putchar(' ');
}
printf("\n");
return;
}
int main(){
int i,j;
nL=read();
nR=read();
bl=nL;br=nR;
nL=max(nL,nR);
nR=nL;
m=read();
int u,v,w;
for(i=;i<=m;i++){
u=read();v=read();w=read();
mp[u][v]=w;
}
KM();
return ;
}