洛谷 5295 [北京省选集训2019]图的难题 题解

发表于 | 阅读次数：
本文字数： 878 字 | 阅读时长 ≈ 4 分钟

题意简述

给你一个 $n$ 个点 $m$ 条边的无向图，判断是否能将一些边染色为白色，其它的染成黑色，并且没有一个纯色的环。

$n\le 501,m\le 2n$

思路

一张图有 $E$ 条边，$V$ 个点。那么，它要满足没有纯色的环，$E$ 最大值为 $2(V-1)$（此时的情况就是白色和黑色分别构成两颗生成树）。

$E\le 2V-2$，可以变成 $E-2V\le -2$。

那么我们现在总的图都要满足条件，那对于任意一个子图当然也满足条件了。我们可以这样转换：$E-2V$ 最大的子图，也满足 $E-2V\le -2$。

那如何求 $E-2V$ 最大的子图呢？把边当成点，点当成边，这就变成了最大权闭合子图问题。

（不会的百度一下）

代码

点击
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 100055
	#define INF 0x5f5f5f5f
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}
	class Graph
	{
	    public:
	        int EdgeCount;
	        int head[N];
	        int To[N],Label[N],Next[N];

	        inline void clear()
	        {
	            MEM(head,-1);
	            EdgeCount=-1;
	        }
	        inline void AddEdge(int u,int v,int w)
	        {
	            ++EdgeCount;
	            To[EdgeCount]=v; Label[EdgeCount]=w; Next[EdgeCount]=head[u];
	            head[u]=EdgeCount;
	        }
	
	        int Source,Sink;
	        int deep[N];
	        queue<int> Q;
	        bool BFS()
	        {
	            while(!Q.empty()) Q.pop();
	            FK(deep);
	
	            Q.push(Source);
	            deep[Source]=1;
	            do
	            {
	                int u=Q.front();Q.pop();
	                for(register int i=head[u];~i;i=Next[i])
	                {
	                    int v=To[i];
	                    if (!deep[v] and Label[i])
	                    {
	                        deep[v]=deep[u]+1;
	                        if (v==Sink) {return true;}
	                        Q.push(v);
	                    }
	                }
	            }while(!Q.empty());
	
	            return (bool)(deep[Sink]);
	        }
	        int DFS(int u,int MinFlow)
	        {
	            if (u==Sink) return MinFlow;

	            int rest=MinFlow;
	            for(register int i=head[u];~i and rest;i=Next[i])
	            {
	                int v=To[i];
	                if (deep[v]==deep[u]+1 and Label[i]!=0)
	                {
	                    int d=DFS(v,min(MinFlow,Label[i]));
	                    if (!d) deep[v]=0;
                        Label[i]-=d;
                        Label[i^1]+=d;
                        rest-=d;
	                }
	            }
	            return MinFlow-rest;
	        }
	        int Dinic()
	        {
	            int ans=0;
	            while(BFS()) ans+=DFS(Source,INF);
	            return ans;
	        }
	}Nt; // 网络流
	
	int n,m;
	int uu[N],vv[N];
	void Input()
	{
		Rd(2,&n,&m);
		F(i,1,m) uu[i]=I(),vv[i]=I();
	}

	#define S Nt.Source
	#define T Nt.Sink
	#define AddFlow(u,v,w) {Nt.AddEdge(u,v,w); Nt.AddEdge(v,u,0);}
    // 建流
	int MustChoose(int s) // 强制选择点 s 的答案
	{
		Nt.clear();
		F(i,1,m) 
		{
			int u=uu[i],v=vv[i];
			AddFlow(S,i,1);
			AddFlow(i,m+u,INF);
			AddFlow(i,m+v,INF);
		}
		F(i,1,n) if (i!=s)
		{
			AddFlow(i+m,T,2);
		}

		return m-2-Nt.Dinic();
	}
	void Soviet()
	{
		S=n+m+1,T=n+m+2;
		int ans=-INF;
		F(i,1,n) 
		{
			ans=max(ans,MustChoose(i)); // 把每个强制选 i 的答案取 max，就是最大闭合子图了
			if (ans>-2) {puts("No"); return;} // 每一个都要 <=-2，有一个 > 就直接输出 No
		}
		
		puts((ans<=-2)?"Yes":"No");
	}

	#define Flan void
	Flan IsMyWife()
	{
		int t=I();
		F(i,1,t)
		{
			Input();
			Soviet();
		}
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w