CF875F Royal Questions[最大生成基环树森林]

这题这场比赛一堆人秒切。。果然还是我太菜了吗

题意：二分图，右边$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),;

 }

总结：简化问题能力不够啊。如果看出是单纯的左边点对二择、无视右边的话，是很容易想出来的。这种简单问题都是可以尝试转化的。

巴特西

CF875F Royal Questions[最大生成基环树森林]

最新文章

热门文章