CF #311 D. Vitaly and Cycle 加最少边形成奇圈

题目链接：http://codeforces.com/problemset/problem/557/D

大意给出一个未必联通的无向图（点数至少为3），问最少加多少边可以形成一个奇圈，以及这样做的方案有多少种。

首先如果是一张没有边的图，那么直接就是需要加三条边，有C(n,3)种方式。

接着，判断这张图每一个联通块是否是一个二分图，因为二分图是一定没有奇圈的。如果有联通块不是二分图，那么也就是意味着存在奇圈，这样的话需要加0条边，方式为1种。

接下去还需要分两种情况讨论

1.如果所有的联通块都只有1个或者2个点，则至少需要加2条边，方式为所有点数为2的联通块随便选择一个其他的点加2条边，故统计所有点数为2的联通块数量。

2.存在至少包含3个点的联通块，注意，此时已经排除了联通块不是二分图的情况，所以也即联通块一定是二分图。对于二分图，连接x部和y部的边是不会形成奇圈的，这种情况下只需要连接一条相同部之间的边即可。所以方案数为对于所有至少包含3个点的联通块，计算x部和y部点数，对答案累加上 C(cntx,2)+C(cnty,2)

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 using namespace std;

 const int N=1e5+;

 vector<int> edge[N];

 bool vis[N];

 int col[N];

 bool found=false;

 int cnt[];

 void dfs(int u,int c) {

     vis[u]=true;

     col[u]=c;

     cnt[c]++;

     for (int i=;i<edge[u].size();i++) {

         int v=edge[u][i];

         if (vis[v]&&col[v]==c) {

             found=true;

         }

         if (vis[v]) continue;

         dfs(v,c^);

     }

 }

 int main(){

     int n,m;

     scanf("%d %d",&n,&m);

     for (int i=;i<=m;i++) {

         int u,v;

         scanf("%d %d",&u,&v);

         edge[u].push_back(v);

         edge[v].push_back(u);

     }

     if (m==) {

         long long ret=1LL*n*(n-)*(n-)/6LL;

         cout<<<<" "<<ret<<endl;

     }

     else {

         found=false;

         bool three=false;

         long long retThree=;

         int cnt2=;

         for (int i=;i<=n&&!found;i++) {

             if (vis[i]) continue;

             cnt[]=cnt[]=;

             dfs(i,);

             if (cnt[]+cnt[]>=){

                 three=true;

                 retThree+=1LL*cnt[]*(cnt[]-)/2LL+1LL*cnt[]*(cnt[]-)/2LL;

             }

             else if (cnt[]+cnt[]==)

                 cnt2++;

         }

         if (found) {

             cout<<<<" "<<<<endl;

         }

         else if (three){

             cout<<<<" "<<retThree<<endl;

         }

         else {

             long long ret=1LL*cnt2*(n-);

             cout<<<<" "<<ret<<endl;

         }

     }

     return ;

 }

巴特西

CF #311 D. Vitaly and Cycle 加最少边形成奇圈

最新文章

热门文章