cf D George and Interesting Graph

题意：给你一个有趣图的定义：在这个图中有一个根，根与每个点都有边和回边，除了根之外，其他的点的出度和入度都为2，然后给你一个图让你经过几步操作可以使此图变为有趣图，操作为：删边或者加边。

思路：枚举根，然后删除与根有关的边，重新建图，用二分图求最大匹配，可以用匈牙利算法，加的边数：满足题中有关根的加边数+（点数-匹配数），删掉的边数：边数-满足题中有关根的使用的边数-匹配时使用的边数。

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 using namespace std;

 const int inf=<<;

 int g[][];

 int n,m;

 bool chk[];

 int match[];

 vector<int>x[];

 int dfs(int p)

 {

     for(int i=; i<(int)x[p].size(); i++)

     {

         int v=x[p][i];

         if(!chk[v])

         {

            chk[v]=true;

            int t=match[v];

            match[v]=p;

            if(t==-||dfs(t))

            {

                return ;

            }

            match[v]=t;

         }

     }

     return ;

 }

 int Pro(int c)

 {

      memset(match,-,sizeof(match));

      int res=;

      for(int i=; i<=n; i++)

      {

          if(i==c) continue;

          memset(chk,false,sizeof(chk));

          res+=dfs(i);

      }

      return res;

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         vector<int>gg[];

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

         {

             int u,v;

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

             gg[u].push_back(v);

             g[u][v]=;

         }

         int ans=inf;

         for(int i=; i<=n; i++)

         {

             int t1=n-gg[i].size();

             for(int j=; j<=n; j++)

             {

                 if(!g[j][i]) t1++;

             }

             if(g[i][i]==) t1--;

             for(int j=; j<=n; j++)

             {

                 x[j].clear();

             }

             int cnt=;

             for(int j=; j<=n; j++)

             {

                 if(j==i) continue;

                 for(int k=; k<(int)gg[j].size(); k++)

                 {

                     int v=gg[j][k];

                     if(v==i)continue;

                     cnt++;

                     x[j].push_back(v);

                 }

             }

             ans=min(ans,t1+cnt+n--*Pro(i));

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

cf D George and Interesting Graph

最新文章

热门文章