題目鏈接：點(diǎn)擊查看

題目大意：給出n個點(diǎn)和m條邊組成的有向圖，現(xiàn)在我們需要找出一個點(diǎn)作為中心點(diǎn)，然后增加或減少邊的條數(shù)以達(dá)到下面的目標(biāo)：

除了中心點(diǎn)外，其他的每個點(diǎn)的入度為2且出度為2

中心點(diǎn)和每個點(diǎn)都必須有兩條邊，一條是正向的，一條是反向的

中心點(diǎn)和自己也必須有一條邊

我們令每次增加一條邊或刪除一條邊都記做一次操作，問如何選取中心點(diǎn)可以使得操作數(shù)達(dá)到最少

題目分析：因?yàn)閚最大只有500，故我們可以枚舉每一個點(diǎn)都成為中心點(diǎn)，然后實(shí)時更新答案即可，接下來的問題就轉(zhuǎn)換成了讓一個點(diǎn)當(dāng)中心點(diǎn)，我們該怎么計(jì)算操作次數(shù)

首先，因?yàn)槌行狞c(diǎn)外每個點(diǎn)的入度和出度都必須是2，并且都需要和中心點(diǎn)有兩條連邊，所以當(dāng)我們將中心點(diǎn)與其他點(diǎn)的邊都暫時性移除之后，剩下的點(diǎn)必須可以組成一個環(huán)才能達(dá)到目標(biāo)，所以我們可以在現(xiàn)有的邊的基礎(chǔ)上，跑一下二分圖最大匹配，讓盡可能多的邊兩兩相連，這樣我們就可以進(jìn)行下一步的計(jì)算了，我們在讀入邊的時候，還需要記錄一下每個點(diǎn)的入度和出度，下面整理一下計(jì)算的方法：

因?yàn)橹行狞c(diǎn)與其余n-1個點(diǎn)都必須連兩條邊，而且自身也要連一條邊，故最后應(yīng)該與中心點(diǎn)相連的邊數(shù)sum_edge=2*(n-1)+1，然后我們當(dāng)前一共有m條邊，這個也是已知條件，還有就是當(dāng)前與中心點(diǎn)相連的邊一共有link_edge=in[i]+out[i]-maze[i][i]條邊，現(xiàn)在我們利用匈牙利算法可以計(jì)算出最大匹配的共有mmax條邊

上面的都作為已知條件使用，接下來我們只需要通過已知條件計(jì)算一下當(dāng)前圖中有多少條邊需要刪除，并且有多少條邊需要增加即可得到答案了：

注意，記得對中心點(diǎn)連到自己的那條邊特判一下，因?yàn)槲覀兦蟪鰜淼膌ink_edge的意義是其余n-1個點(diǎn)與中心點(diǎn)相連的邊數(shù)，不能算上自己連自己的那條邊

增加：

n-1-mmax=add1(在n-1個點(diǎn)組成的環(huán)上一共需要n-1條邊，減去最大匹配的邊數(shù)，就是需要增加多少條邊到環(huán)上)

sum_edge-link_edge=add2(應(yīng)該與中心點(diǎn)相連的邊數(shù))

刪除：

m-link_edge=remain_edge(將與中心點(diǎn)相連的邊暫時性移除后剩余的邊的條數(shù))

remain_edge-mmax=del(在剩余的邊中無法匹配的邊就是沒有用的邊，刪掉即可)

然后答案就是add1+add2+del了，實(shí)時更新即可

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=550;int n,m; int in[N],out[N];bool maze[N][N];int match[N];bool vis[N];bool dfs(int x,int pos) {for(int i=1;i<=n;i++){if(i==pos)continue;if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i],pos)){match[i]=x;return true;}}}return false; }int solve(int pos) {int mmax=0;memset(match,0,sizeof(match));for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(i==pos)continue;if(dfs(i,pos))mmax++;}int link_edge=in[pos]+out[pos]-maze[pos][pos];int sum_edge=2*(n-1)+1;int remain_edge=m-link_edge;int del=remain_edge-mmax;int add1=n-1-mmax;int add2=sum_edge-link_edge;return add1+add2+del; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);maze[u][v]=true;out[u]++;in[v]++;}int ans=inf;for(int i=1;i<=n;i++)ans=min(ans,solve(i));printf("%d\n",ans);return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 387D George and Interesting Graph(二分图最大匹配+暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。