P1330封鎖陽光大學(xué)（染色法）-創(chuàng)新互聯(lián)

題目描述

曹是一只愛刷街的老曹，暑假期間，他每天都?xì)g快地在陽光大學(xué)的校園里刷街。河蟹看到歡快的曹，感到不爽。河蟹決定封鎖陽光大學(xué)，不讓曹刷街。

成都創(chuàng)新互聯(lián)公司從2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站建設(shè)、做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元什邡做網(wǎng)站,已為上家服務(wù),為什邡各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

陽光大學(xué)的校園是一張由?nn?個(gè)點(diǎn)構(gòu)成的無向圖，nn?個(gè)點(diǎn)之間由?mm?條道路連接。每只河蟹可以對(duì)一個(gè)點(diǎn)進(jìn)行封鎖，當(dāng)某個(gè)點(diǎn)被封鎖后，與這個(gè)點(diǎn)相連的道路就被封鎖了，曹就無法在這些道路上刷街了。非常悲劇的一點(diǎn)是，河蟹是一種不和諧的生物，當(dāng)兩只河蟹封鎖了相鄰的兩個(gè)點(diǎn)時(shí)，他們會(huì)發(fā)生沖突。

詢問：最少需要多少只河蟹，可以封鎖所有道路并且不發(fā)生沖突。

輸入格式

第一行兩個(gè)正整數(shù)，表示節(jié)點(diǎn)數(shù)和邊數(shù)。接下來?mm?行，每行兩個(gè)整數(shù)?u,vu,v，表示點(diǎn)?uu?到點(diǎn)?vv?之間有道路相連。

輸出格式

僅一行如果河蟹無法封鎖所有道路，則輸出?Impossible，否則輸出一個(gè)整數(shù)，表示最少需要多少只河蟹。

輸入輸出樣例

輸入 #1復(fù)制

輸出 #1復(fù)制

Impossible

輸入 #2復(fù)制

3 2
1 2
2 3

輸出 #2復(fù)制

說明/提示

【數(shù)據(jù)規(guī)?！?br />對(duì)于?100\%100%?的數(shù)據(jù)，1\le n \le 10^41≤n≤104，1\le m \le 10^51≤m≤105，保證沒有重邊。

思路：

嗚嗚嗚，這道題我真真真真真真真沒啥思路，于是打開了題解看了看大佬們的想法，學(xué)到了一個(gè)新的方法，染色法，大佬的思路是這樣的：

如果一條邊兩個(gè)點(diǎn)一紅一藍(lán)，那就是恰好被切斷
如此看來，所謂占領(lǐng)和不占領(lǐng)其實(shí)是等價(jià)的。
只需要分別嘗試兩種情況（令這個(gè)點(diǎn)是紅色或者令這個(gè)點(diǎn)是藍(lán)色），看看哪種情況中紅點(diǎn)數(shù)目最少即可。
為什么會(huì)Impossible？那是因?yàn)?，在從第一個(gè)點(diǎn)的顏色一直推到所有點(diǎn)的顏色的過程中，有的點(diǎn)會(huì)被要求涂上相反的顏色。即當(dāng)你想把一個(gè)點(diǎn)涂成藍(lán)色的時(shí)候，卻發(fā)現(xiàn)它已經(jīng)是紅色了。這就出現(xiàn)無解情況。
連通是個(gè)永恒的話題。千萬不要忘記對(duì)不連通的考慮

看了大佬的代碼，我真的佩服的五體投地，于是我照葫蘆畫瓢+自我理解完成了這道題

代碼：

#include
using namespace std;
vectorG[10005];
int f=1;
int flag[10005];//-1為沒染色，0為藍(lán)色，1為紅色
int ans=0;
int dfs(int s,int d)
{
?if(f==0)
?{
??? ?return 0;
?}
?else
?{
??? ?int sum=d;
??? ?flag[s]=d;
??? ?for(int j=0;j ??? ?{
??? ??? ?int y=G[s][j];
??? ??? ?if(flag[y]==-1)
??? ??? ?{
??? ??? ??? ?flag[y]=(!d);//這個(gè)寫法真的很酷的好吧，愛死了
??? ??? ??? ?sum=sum+dfs(y,!d);
??? ??? ?}
??? ??? ?else if(flag[y]==d)
??? ??? ?{
??? ??? ??? ?f=0;
??? ??? ?}
??? ?}
??? ?return sum;
?}
}
int main()
{
?int n,m;
?cin>>n>>m;
?memset(flag,-1,sizeof(flag));

? //圖的存儲(chǔ)
?for(int i=1;i<=m;i=i+1)
?{
??? ?int u,v;
??? ?cin>>u>>v;
??? ?G[u].push_back(v);
??? ?G[v].push_back(u);
?}

? //有可能圖不連通（好惡心）
?for(int i=1;i<=n;i=i+1)
?{
??? ?if(flag[i]==-1)
??? ?{

? //分別涂上紅色和藍(lán)色；
??? ??? ?int a=dfs(i,0);
??? ??? ?memset(flag,-1,sizeof(flag));//實(shí)現(xiàn)兩次遍歷并行不悖
??? ??? ?int b=dfs(i,1);
??? ??? ?ans=ans+min(a,b);
??? ?}
??? ?if(f==0)
??? ?{
??? ??? ?break;
??? ?}
?}
?if(f==0)
?{
??? ?cout<<"Impossbile"< ?}
?else
?{
??? ?cout< ?? ?}
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：P1330封鎖陽光大學(xué)（染色法）-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://bm7419.com/article20/hceco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、軟件開發(fā)、App設(shè)計(jì)、域名注冊(cè)、自適應(yīng)網(wǎng)站、微信小程序

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容