7.16

luogu日报精选

今日目标

【16NOIP提高组】玩具谜题 check
【06NOIP提高组】2^k进制数
【15NOIP提高组】子串

下午图论专题：

最小生成树
最短路

日常刷USACO

学习

组合数学

P1330 封锁阳光大学

/*
translation:
	有一些白点，现将一些白点染为黑点，使得:黑点互不相邻且白点互不相邻。要求最少黑点数。
solution:
	黑白间隔染色，就是枚举该连通分量的所有点，与该点相邻的点染为与其不同的颜色，然后累加黑色点数与白色点数的最小值，若不能实现这种染色方法，说明矛盾。
trigger:
	
note:
	*bfs 染色 
date:
	2019.07.16
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,x) for(int i=head[x];i;i=e[i].next)

#define N 100005
struct node{
    int v,next;
}e[N<<1];

int head[N<<1],cnt;
int sum[2],col[N];//sum表示两种涂色方法，col表示颜色 
bool vis[N];

void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}

void dfs(int u,int b_w){
	vis[u]=1;//表示已经遍历过 
	sum[b_w]++;//此颜色的个数加1 
	col[u]=b_w;//涂色 
	ee(i,u){
		int v=e[i].v;
		if(vis[v]){
			if(col[v]==b_w^1)continue;//颜色和原来不同 
			else {//颜色和原来相同 
				printf("Impossible");
				exit(0);
			}
		}
		else 
			dfs(v,b_w^1);
	}
}

int main(){
    int n,m;
    rd(n),rd(m);
    int ans=0;
    rep(i,1,m){
        int u,v;rd(u),rd(v);
        add(u,v),add(v,u);
    }
    rep(i,1,n){
        sum[0]=sum[1]=0;//初始化 
        if(!vis[i])
            dfs(i,0);
        ans+=min(sum[0],sum[1]);//选择个数更小的那种涂色方案 
    }
    printf("%d",ans);
    return 0;
}