我一开始把源点往初始白点建边,从结束白点往汇点建边,一直卡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;
}