CSU 1574 Amanda Lounges 模拟题
来源：程序员人生 发布时间：2015-05-27 07:48:09 阅读次数：3435次
题目链接：点击打开链接
题意：
给定n个点m条边的无向图（开始每一个点都是白色）
下面m行给出边和边权，边权表示这条边所连接的2个点中被染成黑色的点数。
0表示染，1表示其中1个点染，2表示都染。
问：最少染多少个点可以满足上述的边权。若不存在输出impossible
首先处理所有边权为0和2的情况。
这样处理后图中就只剩下边权为1的子图。
任意染1个点，然后bfs1下把子图染掉便可。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?⑴:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
const int N = 200105;
const int M = N<<1;
typedef pair<int,int> pii;
vector<pii>G;
struct Edge{
int from, to, col, nex;
}edge[M];
//注意 N M 要修改
int head[N], edgenum;
void add(int u, int v, int col){
Edge E = {u, v, col, head[u]};
edge[edgenum] = E;
head[u] = edgenum ++;
}
void init(){
memset(head, ⑴, sizeof head); edgenum = 0;
}
int c[N], ans, n, m;
int bfs(int x){
int siz = 1, ran = 1; c[x] = 1;
queue<int>q;
q.push(x);
// printf("bfs:%d's color = %d
", x, c[x]);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
// printf("bfs_edge(%d,%d)-(%d,%d)
", u, c[u], v, c[v]);
if(c[v]!=⑴){
// printf("sum = %d
", c[u]+c[v]);
if((c[u]+c[v])!=1)return ⑴;
}
else {
siz++;
c[v] = c[u]^1;
ran += c[v];
q.push(v);
// printf("%d's color = %d
", v, c[v]);
}
}
}
return min(ran, siz-ran);
}
bool solve(){
int u, v, d;
memset(c, ⑴, sizeof c);
for(int i = 0; i < m; i++){
rd(u); rd(v); rd(d);
add(u, v, d);
add(v, u, d);
}
queue<int>q;
for(int i = 0; i < edgenum; i+=2){
u = edge[i].from; v = edge[i].to; d = edge[i].col;
if(d == 0){
if(c[u]==1 || c[v] == 1)return false;
if(c[u]==⑴)q.push(u), c[u] = 0;
if(c[v]==⑴)q.push(v), c[v] = 0;
}
else if(d == 2){
if(c[u] == 0 || c[v] == 0)return false;
if(c[u]==⑴)q.push(u), c[u] = 1;
if(c[v]==⑴)q.push(v), c[v] = 1;
}
}
while(!q.empty()){
u = q.front(); q.pop();
for(int i = head[u];~i;i=edge[i].nex){
v = edge[i].to;
if(c[v]!=⑴){
if(edge[i].col != c[u]+c[v])return false;
}
else {
c[v] = c[u]^1;
q.push(v);
}
}
}
// puts("init:"); for(int i = 1; i <= n; i++)printf("(%d'color is %d)
", i, c[i]);
for(int i = 1; i <= n; i++)ans += c[i] == 1;
G.clear();
for(int i = 0; i < edgenum; i+=2){
if(edge[i].col != 1)continue;
u = edge[i].from; v = edge[i].to;
if(c[u]==⑴ && c[v]==⑴)G.push_back(pii(u,v));
}
init();
for(int i = 0; i < (int)G.size(); i++){
u = G[i].first; v = G[i].second; add(u,v,1); add(v,u,1);
// printf("addedge (%d,%d)
", u, v);
}
for(int i = 1; i <= n; i++)
if(c[i] == ⑴){
int tmp = bfs(i);
if(tmp == ⑴)return false;
ans += tmp;
}
return true;
}
int main(){
while(~scanf("%d %d", &n, &m)){
init();
ans = 0;
if(false == solve())puts("impossible");
else cout<<ans<<endl;
}
return 0;
}
/*
5 4
1 2 2
2 3 1
3 4 1
4 5 1
ans:3
5 5
1 2 2
2 3 1
3 4 1
4 5 1
3 5 1
ans:im
5 6
1 2 2
2 3 1
3 4 1
4 5 1
3 6 0
5 6 0
ans:3
9 8
1 2 2
2 3 1
3 4 1
4 5 1
3 6 0
5 6 0
7 8 1
8 9 1
ans:4
9 9
1 2 2
2 3 1
3 4 1
4 5 1
3 6 0
5 6 0
7 8 1
8 9 1
9 7 1
ans:im
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
