CSU 1574 Amanda Lounges 模擬題
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-05-27 07:48:09 閱讀次數(shù)：3741次
題目鏈接：點(diǎn)擊打開(kāi)鏈接
題意：
給定n個(gè)點(diǎn)m條邊的無(wú)向圖（開(kāi)始每一個(gè)點(diǎn)都是白色）
下面m行給出邊和邊權(quán)，邊權(quán)表示這條邊所連接的2個(gè)點(diǎn)中被染成黑色的點(diǎn)數(shù)。
0表示染，1表示其中1個(gè)點(diǎn)染，2表示都染。
問(wèn)：最少染多少個(gè)點(diǎn)可以滿足上述的邊權(quán)。若不存在輸出impossible
首先處理所有邊權(quán)為0和2的情況。
這樣處理后圖中就只剩下邊權(quán)為1的子圖。
任意染1個(gè)點(diǎn)，然后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
*/
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
