（思維+圖論）
C. Peaceful Rooks
題目傳送門：
C. Peaceful Rooks
題目大意：
給你一個n*n的棋盤，有m個棋子（m<n）每個棋子都在不同的行和列，每個棋子可以進行水平和豎直移動，問最少移動多少次使得每個棋子位于棋盤的主對角線上，
思路：
如果是本來就位于對角線上的點，那么自然就沒有必要進行移動了，否則就是在浪費操作次數，
那么不在對角線上的點一定需要操作一次，豎直移動或者水平移動到對角線上，
但是我們還發現可能會有n個點構成一個環，就像樣例3一樣，這個時候我們可以先把其中一個點移到空的行或列上，然后剩下的n-1個點移到對角線上，然后再把原來一出去的那個點移回到對角線上，所以當n個點夠成一個環時，他們的貢獻是n+1，到這里這個題目就轉化成了一個圖論問題，
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int vis[N];
int dfs(int x,int fa)
{
vis[x]=1;
for(int i=0;i<g[x].size();i++)
{
if(g[x][i]==fa) continue;
if(vis[g[x][i]]==1) return 1;
dfs(g[x][i],x);
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
int ans=0;
for(int i=0;i<=n;i++)
{
g[i].clear();
vis[i]=0;
}
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
g[x].push_back(y);
g[y].push_back(x);
ans++;
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
int k=dfs(i,0);
ans=ans+k;
}
}
printf("%d\n",ans);
}
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238626.html
標籤：其他