MnZn刚学网络流求助
查看原帖
MnZn刚学网络流求助
53769
北文楼主2023/5/11 19:51

我一开始把源点往初始白点建边,从结束白点往汇点建边,一直卡90pts。

#include<bits/stdc++.h>
using namespace std;
const int N=10100, inf=2147483647;
int n, m, S, T;
struct Edge{
	int v, nxt, w, c;
}e[2000500];
int h[N], cnt=1;
void add(int u, int v, int w, int c) {
	e[++cnt]=Edge{v, h[u], w, c};
	h[u]=cnt;
	e[++cnt]=Edge{u, h[v], 0, -c};
	h[v]=cnt;
}
int pre[N], lp[N];
int dis[N], flow[N];
bool in[N];
queue<int>t;
int spfa() {
	for(int i=0; i<=T; i++)
		dis[i]=inf, flow[i]=0;
	flow[S]=inf; dis[S]=0;
	t.push(S); in[S]=1;
	while(!t.empty()) {
		int u=t.front(); t.pop();
		in[u]=0;
		int v;
		for(int i=h[u]; i; i=e[i].nxt) {
			if(e[i].w&&dis[v=e[i].v]>dis[u]+e[i].c) {
				dis[v]=dis[u]+e[i].c;
				flow[v]=min(flow[u], e[i].w);
				lp[v]=i; pre[v]=u;
				if(!in[v]) {
					in[v]=1;
					t.push(v);
				}
			}
		}
	}
	return flow[T];
}
char s[55];
int id(int x, int y) {
	return (x-1)*m+y;
}
int dx[]={1, 1, 1, -1, -1, -1, 0, 0};
int dy[]={-1, 0, 1, -1, 0, 1, -1, 1};
int col1[55][55], col[55][55], s1, s2;
int main() {
	scanf("%d %d", &n, &m);
	S=0, T=n*m*2+1;
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			if(s[j]=='0') add(S, id(i, j), 1, 0), s1++;
			col1[i][j]=s[j]-'0';
		}
	}
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			if(s[j]=='0') add(id(i, j), T, 1, 0), s2++;
			col[i][j]=s[j]-'0';
		}
	}
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			int k=s[j]-'0';
			add(id(i, j), id(i, j)+n*m, k/2, 0);
			if(col[i][j]!=col1[i][j]&&(k&1))
				add(id(i, j), id(i, j)+n*m, 1, 0);
			for(int l=0; l<8; l++) {
				int x=i+dx[l], y=j+dy[l];
				if(x<1||x>n||y<1||y>m) continue;
				add(id(i, j)+n*m, id(x, y), inf, 1);
				}
			}
		}
	if(s1!=s2) {
		printf("-1");
		return 0;
	} 
	int d, ans=0, cans=0;
	while(d=spfa()) {
		int u=T;
		while(u!=S) {
			int lst=pre[u];
			e[lp[u]].w-=d;
			e[lp[u]^1].w+=d;
			u=lst;
		}
		ans+=d; cans+=d*dis[T];
	}
	if(ans!=s1) printf("-1");
	else printf("%d", cans);
	return 0;
}

后来我只把源点向需要调整的白点建边,把黑点变成白点的向汇点建边,就100pts了,这是为什么?

#include<bits/stdc++.h>
using namespace std;
const int N=10100, inf=2147483647;
int n, m, S, T;
struct Edge{
	int v, nxt, w, c;
}e[2000500];
int h[N], cnt=1;
void add(int u, int v, int w, int c) {
	e[++cnt]=Edge{v, h[u], w, c};
	h[u]=cnt;
	e[++cnt]=Edge{u, h[v], 0, -c};
	h[v]=cnt;
}
int pre[N], lp[N];
int dis[N], flow[N];
bool in[N];
queue<int>t;
int spfa() {
	for(int i=0; i<=T; i++)
		dis[i]=inf, flow[i]=0;
	flow[S]=inf; dis[S]=0;
	t.push(S); in[S]=1;
	while(!t.empty()) {
		int u=t.front(); t.pop();
		in[u]=0;
		int v;
		for(int i=h[u]; i; i=e[i].nxt) {
			if(e[i].w&&dis[v=e[i].v]>dis[u]+e[i].c) {
				dis[v]=dis[u]+e[i].c;
				flow[v]=min(flow[u], e[i].w);
				lp[v]=i; pre[v]=u;
				if(!in[v]) {
					in[v]=1;
					t.push(v);
				}
			}
		}
	}
	return flow[T];
}
char s[55];
int id(int x, int y) {
	return (x-1)*m+y;
}
int dx[]={1, 1, 1, -1, -1, -1, 0, 0};
int dy[]={-1, 0, 1, -1, 0, 1, -1, 1};
int col1[55][55], col[55][55], s1, s2, fans;
int main() {
	scanf("%d %d", &n, &m);
	S=0, T=n*m*2+1;
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			if(s[j]=='0') s1++;
			col1[i][j]=s[j]-'0';
		}
	}
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			if(s[j]=='0') s2++;
			col[i][j]=s[j]-'0';
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(!col1[i][j]&&col[i][j])
				add(S, id(i, j), 1, 0), fans++;
			if(col1[i][j]&&!col[i][j])
				add(id(i, j)+n*m, T, 1, 0);
		}
	}
	for(int i=1; i<=n; i++) {
		scanf("%s", s+1);
		for(int j=1; j<=m; j++) {
			int k=s[j]-'0';
			add(id(i, j), id(i, j)+n*m, k/2, 0);
			if(col[i][j]!=col1[i][j]&&(k&1))
				add(id(i, j), id(i, j)+n*m, 1, 0);
			for(int l=0; l<8; l++) {
				int x=i+dx[l], y=j+dy[l];
				if(x<1||x>n||y<1||y>m) continue;
				add(id(i, j)+n*m, id(x, y), inf, 1);
				}
			}
		}
	if(s1!=s2) {
		printf("-1");
		return 0;
	} 
	int d, ans=0, cans=0;
	while(d=spfa()) {
		int u=T;
		while(u!=S) {
			int lst=pre[u];
			e[lp[u]].w-=d;
			e[lp[u]^1].w+=d;
			u=lst;
		}
		ans+=d; cans+=d*dis[T];
	}
	if(ans!=fans) printf("-1");
	else printf("%d", cans);
	return 0;
}
2023/5/11 19:51
加载中...