题解 封锁阳光大学

发表于 | 更新于 | 分类于 | 阅读次数：

题目链接

问如何用最少的染色使得所有边的某一个端点被染过了，且不能两个都染过。

一开始以为是DP，后来发现没有DP的方法。。。

最坑的是图还不连通。。

后来发现只需要把图的顶点染成两种颜色且不相邻。对于每一个连通块，答案加上黑色和白色中较小的那个值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
namespace Sonoda
{
	template<typename T> void swap(T &a,T &b)
	{
		T t;
		t=a;
		a=b;
		b=t;
	}
	template<typename T> T GCD(T a,T b)
	{
		if(b==0)
		{
			return a;
		}
		return GCD(b,a%b);
	}
	template<typename T>T Qpow(T a,T b,T p)
	{
		T res=1;
		while(b)
		{
			if(b&1)
			{
				res*=a;
				res%=p;
				b--;
			}
			else
			{
				a*=a;
				a%=p;
				b>>=1;
			}
		}
		return res;
	}
	template <typename T> void Ex_GCD(T a,T b,T &x,T &y)
	{
		if(b==0)
		{
			x=1;
			y=0;
			return;
		}
		Ex_GCD(b,a%b,x,y);
		T t=x;
		x=y;
		y=t-a/b*y;
	}
	template<typename T> inline T read()
	{
		T num = 0, w = 1;
		char c = 0;
		while (c != '-' && !isdigit(c)) c = getchar();
		if (c == '-') w = -1, c = getchar();
		while (isdigit(c)) num = num * 10 + c - '0', c = getchar();
		return num * w;
	}
	template<typename T> inline void write(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x / 10) write(x / 10);
		putchar(x % 10 + '0');
	}
}
const int MAXN=200005;
struct EDGE
{
	int _next,to;
};
EDGE edge[MAXN];
int head[MAXN],col[MAXN],_count;
int vis[MAXN],co1,co0;
void Add_Line(const int &a,const int &b)
{
	_count++;
	edge[_count].to=b;
	edge[_count]._next=head[a];
	head[a]=_count;
}
void DFS(int NowNode,int color)
{
	col[NowNode]=color;
	vis[NowNode]=true;
	if(color)
	{
		co1++;
	}
	else
	{
		co0++;
	}
	for(int i=head[NowNode];i;i=edge[i]._next)
	{
		int NextNode=edge[i].to;
		if(col[NextNode]==color)
		{
			printf("Impossible");
			exit(0);
		}
		if(vis[NextNode])
		{
			continue;
		}
		DFS(NextNode,!color);
	}
}
int ans;
int main()
{
	memset(col,INF,sizeof(col));
	int N,M;
	N=Sonoda::read<int>();
	M=Sonoda::read<int>();
	for(int i=1;i<=M;i++)
	{
		int a,b;
		a=Sonoda::read<int>();
		b=Sonoda::read<int>();
		Add_Line(a,b);
		Add_Line(b,a);
	}
	for(int i=1;i<=N;i++)
	{
		if(!vis[i])
		{
			co1=0;
			co0=0;
			DFS(i,1);
			ans+=min(co1,co0);
		}
	}
	printf("%d",ans);
	return 0;
}

算一道好题，有一定的重做价值。