这题这场比赛一堆人秒切。。果然还是我太菜了吗
题意：二分图，右边$m$个点每个点$i$向左边有且仅有两条连边，边权都是$a_i$。求最大匹配。
一个朴素思想，二分图匹配，用贪心带匈牙利搞一搞，但是复杂度$O(mn)$。`````
注意字眼“只能选一次”。对于同一个点连出的两条边只能择一。也就是说，左边由若干个点对，每选其一有一个代价。那么，不妨将这个点对连边，$x\to y$，则表示$y$被选了。这样，每个点最多只能被选一次，入度至多为1，也就是说是一个最大的基环树和树的森林，然后套板子就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=2e5+;
struct thxorz{
int u,v,w;
inline bool operator <(const thxorz&A)const{return w<A.w;}
}e[N];
int cir[N],anc[N];
int n,m,ans;
inline int get_anc(int x){return anc[x]==x?x:anc[x]=get_anc(anc[x]);} int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
read(n),read(m);
for(register int i=;i<=m;++i)read(e[i].u),read(e[i].v),read(e[i].w);
for(register int i=;i<=n;++i)anc[i]=i;
sort(e+,e+m+);
for(register int i=m;i;--i){
int fu=get_anc(e[i].u),fv=get_anc(e[i].v);
if(fu==fv){
if(!cir[fu])cir[fu]=,ans+=e[i].w;
}
else{
if(!cir[fu]||!cir[fv])cir[fv]=cir[fu]|cir[fv],anc[fu]=fv,ans+=e[i].w;
}
}
return printf("%d\n",ans),;
}
总结：简化问题能力不够啊。如果看出是单纯的左边点对二择、无视右边的话，是很容易想出来的。这种简单问题都是可以尝试转化的。