【Uva 11080】Place the Guards
The UVa Place
2023-09-14 09:03:49 时间
一些城市,之间有道路相连,现在要安放警卫,警卫能看守到当前点周围的边,一条边只能有一个警卫看守,问是否有方案,如果有最少放几个警卫.
二分图;
如果某个连通块不能形成二分图->不行!
如果能形成二分图.
则看看是在染成颜色0的位置放守卫还是在1的位置放守卫;
如果连通块只有1个的话,答案是1而不是0;
因为有说所有的点也要覆盖到的。
这题和最小点覆盖不同,最小点覆盖的话,两个取的点之间可以有边相连
最小点覆盖也没有涉及到单个的点的处理。
0
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x+1)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 200;
int n,m,color[N+20],cnt[2],ans;
vector <int> G[N+20];
int dfs(int x,int c){
color[x] = c;
cnt[c]++;
int len = G[x].size(),bo = 1;
rep1(i,0,len-1){
int y = G[x][i];
if (color[y]==-1)
bo &= dfs(y,1-c);
else
if (color[y]==color[x])
return 0;
}
return bo;
}
int main(){
//Open();
//Close();
int T;
ri(T);
while (T--){
rep1(i,1,N) G[i].clear();
ri(n),ri(m);
rep1(i,1,m){
int x,y;
ri(x),ri(y);
x++,y++;
G[x].pb(y),G[y].pb(x);
}
ans = 0;
int ok = 1;
ms(color,255);
rep1(i,1,n)
if (color[i]==-1){
cnt[0] = 0,cnt[1] = 0;
ok &= dfs(i,0);
if (cnt[0] + cnt[1] == 1){
ans+=1;
}else
ans+=min(cnt[0],cnt[1]);
}
if (!ok)
puts("-1");
else
oi(ans),puts("");
}
return 0;
}
相关文章
- SqlBulkCopy – The given value of type String from the data source cannot be converted to type
- The method setPositiveButton(int, DialogInterface.OnClickListener) in the type AlertDialog.
- 解决The HTTP request is not acceptable for the requested resource
- 【错误记录】Android Studio 创建报错 ( The length of the module location exceeds the limit of 100 characters. )
- ICOM6012 Topic 2 The Big Picture
- ORA-24194: attempt to read data in a message as the wrong type ORACLE 报错 故障修复 远程处理
- ORA-48487: The internal predicate string exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-010861; Symbol: ER_TURNING_LOGGING_OFF_FOR_THE_DURATION; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-08119: The new initrans will make the index too big ORACLE 报错 故障修复 远程处理
- Linux Policy: Unleashing the OpenSource Potential.(linuxpolicy)
- 行界面并掌握常用命令Note: The original prompt mentions 25character title but the provided Chinese alternative mentions 25word title. This response assumes the latter is the intended instruction.(怎样进入linux命令)
- Liri Linux: Unleashing the Power of Open Source Platforms.(lirilinux)
- Exploring the Dynamic Duo: The Power of Solr MongoDB Integration(solrmongodb)
- Exploring the Power of MongoDB: The Definitive Guide to Upgrading Arrays(mongodb更新数组)
- Unlocking the Power of Oracle SP: Streamlining Your Database Management(oraclesp)
- Exploring the Merits of Linux in PCB Design(linuxpcb)
- Introduction to Linux LVM and How to Extend LVM with the PE Concept(linuxlvmpe)
- Exploring the Versatile Applications of Linux Operating Systems(linux操作系统的应用)
- Exploring the Advantages of GPL for Linux: An OpenSource Revolution(gpllinux)
- Discover the Benefits of Oracle ERP Through Insightful Videos(oracleerp视频)
- 优化技巧 (Note The title provided by the AI is incomplete Heres a suggestion for a title that completes the phrase)