公司内部 网站开发,建站工具cms,wordpress 百度分享插件,网站群管理平台建设题目描述
曹是一只爱刷街的老曹#xff0c;暑假期间#xff0c;他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹#xff0c;感到不爽。河蟹决定封锁阳光大学#xff0c;不让曹刷街。
阳光大学的校园是一张由 n 个点构成的无向图#xff0c;n 个点之间由 m 条道…题目描述
曹是一只爱刷街的老曹暑假期间他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹感到不爽。河蟹决定封锁阳光大学不让曹刷街。
阳光大学的校园是一张由 n 个点构成的无向图n 个点之间由 m 条道路连接。每只河蟹可以对一个点进行封锁当某个点被封锁后与这个点相连的道路就被封锁了曹就无法在这些道路上刷街了。非常悲剧的一点是河蟹是一种不和谐的生物当两只河蟹封锁了相邻的两个点时他们会发生冲突。
询问最少需要多少只河蟹可以封锁所有道路并且不发生冲突。
题目限制 输入格式
第一行两个正整数表示节点数和边数。 接下来 m 行每行两个整数 u,v表示点 u 到点 v 之间有道路相连。
输出格式
仅一行如果河蟹无法封锁所有道路则输出 Impossible否则输出一个整数表示最少需要多少只河蟹。
输入输出样例 解题思路
因为螃蟹不能相邻所以本题用染色法再结dfs解决问题
AC代码
#include bits/stdc.h
using namespace std;
vectorint E[10010];
int n,m,x,c[10010],f[10010];
void dfs(int u,int t);
int main()
{int u,v,ans0;cinnm;memset(c,-1,sizeof(c));while(m--){cinuv;E[u].push_back(v);E[v].push_back(u);}memset(f,0,sizeof(c));for(int i1;in;i)if(f[i]0){ //没搜过的就搜x0;memset(c,-1,sizeof(c));dfs(i,0);int t0;for(int i1;in;i) tc[i]1;ansmin(t,x-t); //累加答案时要注意比较最优解}printf(%d,ans);return 0;
}
void dfs(int u,int t)
{if(c[u]!-1c[u]!t){puts(Impossible);exit(0);}if(c[u]t)return;c[u]t; //染色f[u]1; //标记x;for(int i0;iE[u].size();i)dfs(E[u][i],t^1);
}
