首页 > 代码库 > cf D George and Interesting Graph

cf D George and Interesting Graph

2024-11-14 20:59:39   203人阅读

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

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

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 const int inf=1<<29; 7  8 int g[600][600]; 9 int n,m;10 bool chk[600];11 int match[600];12 vector<int>x[600];13 14 int dfs(int p)15 {16     for(int i=0; i<(int)x[p].size(); i++)17     {18         int v=x[p][i];19         if(!chk[v])20         {21            chk[v]=true;22            int t=match[v];23            match[v]=p;24            if(t==-1||dfs(t))25            {26                return 1;27            }28            match[v]=t;29         }30     }31     return 0;32 }33 34 int Pro(int c)35 {36      memset(match,-1,sizeof(match));37      int res=0;38      for(int i=1; i<=n; i++)39      {40          if(i==c) continue;41          memset(chk,false,sizeof(chk));42          res+=dfs(i);43      }44      return res;45 }46 47 int main()48 {49     while(scanf("%d%d",&n,&m)!=EOF)50     {51         vector<int>gg[600];52         for(int i=1; i<=m; i++)53         {54             int u,v;55             scanf("%d%d",&u,&v);56             gg[u].push_back(v);57             g[u][v]=1;58         }59         int ans=inf;60         for(int i=1; i<=n; i++)61         {62             int t1=n-gg[i].size();63             for(int j=1; j<=n; j++)64             {65                 if(!g[j][i]) t1++;66             }67             if(g[i][i]==0) t1--;68             for(int j=1; j<=n; j++)69             {70                 x[j].clear();71             }72             int cnt=0;73             for(int j=1; j<=n; j++)74             {75                 if(j==i) continue;76                 for(int k=0; k<(int)gg[j].size(); k++)77                 {78                     int v=gg[j][k];79                     if(v==i)continue;80                     cnt++;81                     x[j].push_back(v);82                 }83             }84             ans=min(ans,t1+cnt+n-1-2*Pro(i));85         }86         printf("%d\n",ans);87     }88     return 0;89 }
View Code

 

cf D George and Interesting Graph


联系
我们