反正就是也不懂：
Universal Online Judge：#81. 一般图最大权匹配：
从前一个和谐的班级，所有人都是搞OI的。有 n 个是男生，有 0 个是女生。男生编号分别为 1,…,n。
现在老师想把他们分成若干个两人小组写动态仙人掌，一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。
有若干个这样的条件：第 v 个男生和第 u 个男生愿意组成小组，并能写出 w 万万行的代码。
请问这个班级里的动态仙人掌的总代码量最多是多少？
输入格式
第一行两个正整数，n,m。保证 n≥2。
接下来 mm 行，每行三个整数 v,u,w 表示第 v 个男生和第 u 个男生愿意组成小组，且能写出 w 万万行的代码。保证 1≤v,u≤n，保证v≠u，保证同一对 v,u 不会出现两次（这里是无序对）。
输出格式
第一行一个整数，表示总代码量最多是多少（单位是万万行）。
接下来一行 n 个整数，描述一组最优方案。第 v 个整数表示 v 号男生所在小组的另一个男生的编号。如果 v 号男生没有小组请输出 0。
样例一
input
7 20
5 7 9
3 7 4
3 6 6
2 5 8
5 1 9
1 3 6
6 5 1
2 7 4
2 3 5
6 4 2
7 1 5
5 4 4
4 1 3
5 3 9
7 6 4
2 1 3
4 3 9
6 2 7
4 2 8
6 1 10
output
28
6 0 4 3 7 1 5
限制与约定
1≤n≤400，1≤m≤798001≤w≤5×108。
时间限制：2s
空间限制：256MB
不要求最大匹配，要求是匹配，且最大权
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=620; //内存开点数的1.5倍
const int inf=0x3f3f3f3f;
struct node
{
int x,y,z;
node(){}
node(int a,int b,int c)
{
x=a,y=b,z=c;
}
}g[maxn][maxn];
int n,m,nx,t,lab[maxn],match[maxn],slack[maxn];
int st[maxn],pa[maxn],flower_from[maxn][maxn],S[maxn],vis[maxn];
vector<int>flower[maxn];
deque<int>q;
int dist(node e)
{
return lab[e.x]+lab[e.y]-g[e.x][e.y].z*2;
}
void update_slack(int x,int y)
{
if(!slack[y]||dist(g[x][y])<dist(g[slack[y]][y]))
slack[y]=x;
}
void set_slack(int y)
{
slack[y]=0;
for(int x=1;x<=n;x++)
if(g[x][y].z>0&&st[x]!=y&&S[st[x]]==0)
update_slack(x,y);
}
void q_push(int x)
{
if(x<=n) return q.push_back(x);
for(int i=0;i<flower[x].size();i++) q_push(flower[x][i]);
}
void set_st(int x,int b)
{
st[x]=b;
if(x<=n) return;
for(int i=0;i<flower[x].size();i++) set_st(flower[x][i],b);
}
int get_pr(int b,int xr)
{
int pr=find(flower[b].begin(),flower[b].end(),xr)-flower[b].begin();
if(pr%2==1)
{
reverse(flower[b].begin()+1,flower[b].end());
return flower[b].size()-pr;
}
else return pr;
}
void set_match(int x,int y)
{
match[x]=g[x][y].y;
if(x<=n) return;
node e=g[x][y];
int xr=flower_from[x][e.x],pr =get_pr(x,xr);
for(int i=0;i<pr;i++)
set_match(flower[x][i],flower[x][i^1]);
set_match(xr,y);
rotate(flower[x].begin(),flower[x].begin()+pr,flower[x].end());
}
void augment(int x,int y)
{
int xnv=st[match[x]];
set_match(x,y);
if(!xnv) return;
set_match(xnv,st[pa[xnv]]);
augment(st[pa[xnv]],xnv);
}
int get_lca(int x,int y)
{
for(++t;x||y;swap(x,y))
{
if(x==0) continue;
if(vis[x]==t) return x;
vis[x]=t;
x=st[match[x]];
if(x) x=st[pa[x]];
}
return 0;
}
void add_blossom(int x,int lca,int y)
{
int b=n+1;
while(b<=nx&&st[b]) b++;
if(b>nx) nx++;
lab[b]=0,S[b]=0;
match[b]=match[lca];
flower[b].clear();
flower[b].push_back(lca);
for(int xx=x,yy;xx!=lca;xx=st[pa[yy]])
flower[b].push_back(xx),flower[b].push_back(yy=st[match[xx]]),q_push(yy);
reverse(flower[b].begin()+1,flower[b].end());
for(int xx=y,yy;xx!=lca;xx=st[pa[yy]])
flower[b].push_back(xx),flower[b].push_back(yy=st[match[xx]]),q_push(yy);
set_st(b,b);
for(int xx=1;xx<=nx;xx++) g[b][xx].z=g[xx][b].z=0;
for(int xx=1;xx<=n;xx++) flower_from[b][xx]=0;
for(int i=0;i<flower[b].size();i++)
{
int xs=flower[b][i];
for(int xx=1;xx<=nx;xx++)
if(g[b][xx].z==0||dist(g[xs][xx])<dist(g[b][xx]))
g[b][xx]=g[xs][xx],g[xx][b]=g[xx][xs];
for(int xx=1;xx<=n;xx++)
if(flower_from[xs][xx]) flower_from[b][xx]=xs;
}
set_slack(b);
}
void expand_blossom(int b)
{
for(int i=0;i<flower[b].size();i++ )
set_st(flower[b][i],flower[b][i]);
int xr=flower_from[b][g[b][pa[b]].x],pr=get_pr(b,xr);
for(int i=0;i<pr;i+=2)
{
int xs=flower[b][i],xns=flower[b][i+1];
pa[xs]=g[xns][xs].x;
S[xs]=1,S[xns]=0;
slack[xs]=0,set_slack(xns);
q_push(xns);
}
S[xr]=1,pa[xr]=pa[b];
for(int i=pr+1;i<flower[b].size();i++)
{
int xs=flower[b][i];
S[xs]=-1,set_slack(xs);
}
st[b] = 0;
}
bool on_found_edge(const node &e)
{
int x=st[e.x],y=st[e.y];
if(S[y]==-1)
{
pa[y]=e.x,S[y]=1;
int nu=st[match[y]];
slack[y]=slack[nu]=0;
S[nu]=0,q_push(nu);
}
else if(S[y]==0)
{
int lca=get_lca(x,y);
if (!lca) return augment(x,y),augment(y,x),true;
else add_blossom(x,lca,y);
}
return false;
}
bool matching(void)
{
memset(S,-1,sizeof(S));
memset(slack,0,sizeof(slack));
q.clear();
for(int x=1;x<=nx;x++)
if(st[x]==x&&!match[x]) pa[x]=0,S[x]=0,q_push(x);
if(q.empty()) return false;
while(1)
{
while(q.size())
{
int x=q.front();
q.pop_front();
if(S[st[x]]==1) continue;
for(int y=1;y<=n;y++)
if(g[x][y].z>0&&st[x]!=st[y])
{
if(dist(g[x][y])==0)
{
if(on_found_edge(g[x][y])) return true;
}
else update_slack(x,st[y]);
}
}
int d=inf;
for(int b=n+1;b<=nx;b++)
if(st[b]==b&&S[b]==1) d=min(d,lab[b]/2);
for(int x=1;x<=nx;x++)
if(st[x]==x&&slack[x])
{
if(S[x]==-1) d=min(d,dist(g[slack[x]][x]));
else if(S[x]==0) d=min(d,dist(g[slack[x]][x])/2);
}
for(int x=1;x<=n;x++)
{
if(S[st[x]]==0)
{
if(lab[x]<=d) return false;
lab[x]-=d;
}
else if(S[st[x]]==1) lab[x]+=d;
}
for(int b=n+1;b<=nx;b++)
if(st[b]==b)
{
if(S[st[b]]==0) lab[b]+=d*2;
else if (S[st[b]]==1) lab[b]-=d*2;
}
q.clear();
for(int x=1;x<=nx;x++)
if(st[x]==x&&slack[x]&&st[slack[x]]!=x&&dist(g[slack[x]][x])==0)
if(on_found_edge(g[slack[x]][x])) return true;
for(int b=n+1;b<=nx;b++)
if(st[b]==b&&S[b]==1&&lab[b]==0) expand_blossom(b);
}
return false;
}
pair<ll,int>weight_blossom(void)
{
memset(match,0,sizeof(match));
nx=n;
int n_matches=0;
ll tot_weight=0;
for(int x=0;x<=n;x++)
st[x]=x,flower[x].clear();
int w_max=0;
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++)
{
flower_from[x][y]=(x==y?x:0);
w_max=max(w_max,g[x][y].z);
}
for(int x=1;x<=n;x++) lab[x]=w_max;
while(matching()) ++n_matches;
for(int x=1;x<=n;x++)
if(match[x]&&match[x]<x)
tot_weight+=(ll)g[x][match[x]].z;
return make_pair(tot_weight,n_matches);
}
int main()
{
scanf("%d%d",&n,&m);
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++ )
g[x][y]=node(x,y,0);
int x,y,z;
for(int i=1;i<=m;i++ )
{
scanf ("%d%d%d",&x,&y,&z);
g[x][y].z=g[y][x].z=z;
}
printf ("%lld\n",weight_blossom().first);
for(int i=1;i<=n;i++)
{
if(i!=1) putchar(' ');
printf ("%d",match[i]);
}
putchar('\n');
return 0;
}
京公网安备 11010502036488号