Tag: 最小割

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1934
神犇题解：http://www.cnblogs.com/Tunix/p/4337330.html

解题报告

网上都说这题简单，然而我怎么一点都不觉得啊QAQ
做题的时候，认定是最小割，然而怎么都建不出图
一直想搞成二分图，然而一直搞不成

最后看了题解
感觉这题还是相当不错的！
先假设每一个人都按照原始意图进行了选择
然后再来最小化冲突
具体到建图，可以把赞同的连到S，不赞同的连到T
朋友之间连双向边，因为朋友可能会变卦

这么建图有一个非常形象的理解：
最后和S相连的就是最后赞同的，最后和T相连的就是否决的
那么对于S->T的一条路径：
要么冲突+1，即割掉朋友间的那条边
要么其中一人改变选择，即割掉两侧的边

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300+9;
const int M = N*N*2;
const int INF = 10000000;

int head[N],nxt[M],to[M],flow[M],n,m,dis[N],S,T,cur[N];
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
int DFS(int w, int f) {
    if (w == T) return f;
    else { int ret = 0;
        for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
            int tmp = DFS(to[i], min(f, flow[i]));
            ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
            if (!f) break;
        } return ret;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	n = read(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) if (!read()) Add_Edge(S,i,1); else Add_Edge(i,T,1);
	for (int i=1,a,b;i<=m;i++) a = read(), b = read(), Add_Edge(b,a,1);
	printf("%d\n",Dinic()); 
	return 0;
}

—————————— UPD 2017.7.4 ——————————
好像这题是挺简单的

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=746

好吧，我承认我看的是题解……
推荐这家的题解：https://oi.men.ci/cogs-746/

自己来说的话，就是搞一搞二分图？
染色之后，发现有冲突的点都在不同的集合内
于是连边，跑最小割即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 40000+9;
const int M = N*10;
const int L = 200+9;
const int INF = 10000000;

int head[N],nxt[M],to[M],flow[M],cur[N],dis[N];
int n,m,mat[L][L],vout,S,T; 
int dx[]={0,2,1,-1,-2,-2,-1,1,2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define id(x,y) ((x)+((y)-1)*n)
inline void Add_Edge(int u, int v, int f){
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(S);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
			dis[to[i]] = dis[w] + 1, que.push(to[i]);
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) return f;
	else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
			int tmp = DFS(to[i], min(f, flow[i]));
			ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
			if (!f) break;
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

int main(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	n = read(); m = read(); S = 0; T = N-1; vout = n*n;
	for (int i=1,x,y;i<=m;i++) x = read(), y = read(), mat[x][y] = 1, vout--;
	for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (!mat[i][j]) 
		if ((i+j)&1) {
			Add_Edge(S,id(i,j),1); 
			for (int k=1,x,y;k<=8;k++) {
				x = i + dx[k]; y = j + dy[k];
				if (1 <= x && x <= n && 1 <= y && y <= n && !mat[x][y])
					Add_Edge(id(i,j),id(x,y),INF);
			}
		} else Add_Edge(id(i,j),T,1);
	vout -= Dinic();
	printf("%d\n",vout);
	return 0;
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4519

分治+最小割
具体来说，假设随便选两个点来做一次最小割x
那么左右点被分成了两个点集，而任意一对存在于不同点集的点的最小割与x的割相等
于是只用考虑每个点集内部的点，接下来的事就是坚持信仰了

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;

int head[N],nxt[M],to[M],flow[M],cur[N];
int n,m,vout[N*N],cnt,id[N],dis[N],pur,T=1;
queue<int> que;

inline void Add_Edge(int u, int v, int w) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline bool BFS(int s, int t) {
	memset(dis,-1,sizeof(dis));
	que.push(s); dis[s] = 0;
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) 
			dis[to[i]] = dis[w] + 1, que.push(to[i]);
	}
	return ~dis[t];
}

int DFS(int w, int f) {
	if (w == pur) return f;
	else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
			int tmp = DFS(to[i], min(f, flow[i]));
			flow[i] -= tmp; flow[i^1] += tmp;
			ret += tmp; f -= tmp; if (!f) return ret;
		}
		return ret;
	}	
}

inline int Dinic(int s, int t){
	int ret = 0; pur = t;
	while (BFS(s,t)) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(s,INF);
	} return ret;
}

void SIGN(int w) {
	dis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) 
		if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}

void solve(int l , int r){
	if (l >= r) return ;
	static int tmp[N]; int L=l-1, R=r+1;
	
	for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
	vout[++cnt] = Dinic(id[l],id[r]);
	
	memset(dis,-1,sizeof(dis)); SIGN(id[l]); 
	for (int i=l;i<=r;i++) 
		if (~dis[id[i]]) tmp[++L] = id[i];
		else tmp[--R] = id[i];
	for (int i=l;i<=r;i++) id[i] = tmp[i];
	solve(l,L); solve(R,r);
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v,w;i<=m;i++) u = read(), v = read(), w = read(), Add_Edge(u,v,w);
	for (int i=1;i<=n;i++) id[i] = i; solve(1,n); 
	int tot = 0; sort(vout+1,vout+1+cnt); 
	for (int i=1;i<=cnt;i++) if (vout[i] != vout[i-1]) tot++;
	printf("%d\n",tot);
	return 0;
}