rockdu
很套路的一道题，做过无限之环来看这道题还是十分好想的
因为我比较菜，考试的时候就没能想出来。
按照套路，把格子黑白染色，然后考虑图的特点，到一个地方一定拐弯。
并且，对于一条回路来说，正向和反向的贡献都是一样的。
接下来，我们指定黑、白格子的流向，考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了，我们规定黑格子横进竖出，白格子横出竖进。这样我们把问题抽象成一张图，对于每一个格子可以选择从进向自己连边，自己向出连边，相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件，一个点只能经过一条流量，也就是出入度都是1，想到限制出入度便想到了最小路劲覆盖的模型。
于是，初步的构图便完成了。
1、套用最小路径覆盖模型把每一个格子拆两个点u1, u2。S->u1->u2->T费用都是0，流量都是1，考虑到一个格子不经过的情况，相当于一个自环，所以u1->u2有连边。
2、格子X的连边分为：1、黑色，左右两边是A, B，A1->X2, B1->X2，上下两边是C, D，X1->C2，X1->D2。2、白色，把上面的连边反过来X1->A2, X1->B2, C1->X2, D1->X2
最后，对于必须走的格子，也就是不能有自环，我们去掉中间u1->u2的边即可。
辣鸡题目卡我常数……
把TLE的点删了下面的程序就能过了
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const int maxm = 5e3 + 5;
const int maxn = 2e3 + 5;
const int N = 35;
const int inf = 0x3f3f3f3f;
inline char gc(){
static char buf[5000000], *p1 = buf, *p2 = buf;
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
int f = 1;
inline void read(int & x) {
x = 0, f = 1; static char c = gc();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = gc();
}
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
x *= f;
}
struct edge {
int v, w, cost, next;
} e[maxm << 2];
int head[maxn], cnt;
void adde(const int &u, const int &v, const int &w, const int &cost) {
//cerr << u << "---" << w << "/" << cost << "-->" << v << endl;
e[cnt] = (edge) {v, w, cost, head[u]};
head[u] = cnt++;
e[cnt] = (edge) {u, 0, -cost, head[v]};
head[v] = cnt++;
}
int q[maxn * maxn], frt, bk;
int vis[maxn], fa[maxn], fw[maxn], id[maxn], dis[maxn];
LL dw;
const int Lf = 0, Rt = 1;
int C[N][N], R[N][N], ban[N][N];
int n, m, K, u, v, ND[N][N][2], dcnt, S, T;
int SPFA(int s, int t) {
frt = bk = 1;
q[bk++] = s, vis[s] = 1;
for(register int i = 1; i <= dcnt; ++i)
dis[i] = -inf;
dis[s] = 0;
while(frt < bk) {
int u = q[frt++];
vis[u] = 0;
for(register int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(!e[i].w) continue;
if(dis[v] < dis[u] + e[i].cost) {
dis[v] = dis[u] + e[i].cost;
fa[v] = u, fw[v] = e[i].w, id[v] = i;
if(vis[v]) continue;
q[bk++] = v;
vis[v] = 1;
}
}
}
return dis[t];
}
int Flow(int u, int t, int mn) {
if(u == t) return mn;
mn = Flow(fa[u], t, min(mn, fw[u]));
e[id[u]].w -= mn, e[id[u] ^ 1].w += mn;
return mn;
}
int MaxFlow(int s, int t) {
int ans = 0, f = 0, tmp;
while(SPFA(s, t) != -inf) {
tmp = Flow(t, s, inf), f += tmp;
ans += 1ll * dis[t] * tmp;
}
return f == dw ? ans : -1;
}
int spc[N * N][2];
int main() {
//freopen("bounce.in", "r", stdin);
//freopen("bounce.out", "w", stdout);
int t;
read(t);
while(t--) {
memset(head, -1, sizeof(head));
memset(ban, 0, sizeof(ban));
cnt = 0, dcnt = 0;
read(n), read(m), dw = n * m;
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j < m; ++j)
read(C[i][j]);
for(register int i = 1; i < n; ++i)
for(register int j = 1; j <= m; ++j)
read(R[i][j]);
read(K);
for(register int i = 1; i <= K; ++i) {
read(u), read(v);
ban[u][v] = 1, spc[i][0] = u, spc[i][1] = v;
}
S = ++dcnt, T = ++dcnt;
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j) {
ND[i][j][Lf] = ++dcnt;
ND[i][j][Rt] = ++dcnt;
adde(S, ND[i][j][Lf], 1, 0);
if(!ban[i][j]) adde(ND[i][j][Lf], ND[i][j][Rt], 1, 0);
adde(ND[i][j][Rt], T, 1, 0);
}
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j) {
if((i + j) & 1) { //横进竖出
if(j < m) adde(ND[i][j + 1][Lf], ND[i][j][Rt], 1, C[i][j]);
if(j > 1) adde(ND[i][j - 1][Lf], ND[i][j][Rt], 1, C[i][j - 1]);
if(i < n) adde(ND[i][j][Lf], ND[i + 1][j][Rt], 1, R[i][j]);
if(i > 1) adde(ND[i][j][Lf], ND[i - 1][j][Rt], 1, R[i - 1][j]);
} else { //竖进横出
if(j < m) adde(ND[i][j][Lf], ND[i][j + 1][Rt], 1, C[i][j]);
if(j > 1) adde(ND[i][j][Lf], ND[i][j - 1][Rt], 1, C[i][j - 1]);
if(i < n) adde(ND[i + 1][j][Lf], ND[i][j][Rt], 1, R[i][j]);
if(i > 1) adde(ND[i - 1][j][Lf], ND[i][j][Rt], 1, R[i - 1][j]);
}
}
int ans = MaxFlow(S, T);
if(ans == -1) printf("Impossible\n");
else printf("%d\n", ans);
}
return 0;
}甚至，我贴了份ZKW也没有过，mmp
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const int maxm = 1e4 + 5;
const int maxn = 5e3 + 5;
const int N = 40;
const int inf = 0x3f3f3f3f;
inline char gc(){
static char buf[5000000], *p1 = buf, *p2 = buf;
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
int f = 1;
inline void read(int & x) {
x = 0, f = 1; static char c = gc();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = gc();
}
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
x *= f;
}
LL dw;
const int Lf = 0, Rt = 1;
int C[N][N], R[N][N], ban[N][N];
int n, m, K, u, v, ND[N][N][2], dcnt;
namespace ZKW {
bool vis[maxn];int dist[maxn];
//解释一下各数组的含义：vis两个用处：spfa里的访问标记，増广时候的访问标记，dist是每个点的距离标号
int s,t,ans=0;
//s是起点，t是终点，ans是费用答案
int nedge=-1,p[maxm << 2],c[maxm << 2],cc[maxm << 2],nex[maxm << 2],head[maxn];
//这里是边表，解释一下各数组的含义：p[i]表示以某一点出发的编号为i的边对应点，c表示编号为i的边的流量，cc表示编号为i的边的费用，nex和head不说了吧。。。
inline void addedge(int x,int y,int z,int zz){
p[++nedge]=y;c[nedge]=z;cc[nedge]=zz;nex[nedge]=head[x];head[x]=nedge;
}
inline void adde(int x, int y, int z, int zz){
addedge(x, y, z, zz);
addedge(y, x, 0, -zz);
}
//建边（数组模拟边表倒挂）
int q[maxn * maxn], frt, bk;
inline bool spfa(int s,int t){
memset(vis,0,sizeof vis),frt=bk=1;
for(int i=0;i<=dcnt;i++)dist[i]=1e9;dist[t]=0;vis[t]=1;
//首先SPFA我们维护距离标号的时候要倒着跑，这样可以维护出到终点的最短路径
q[bk++]=t;
//使用了SPFA的SLF优化（SLF可以自行百度或Google）
while(frt<bk){
int now=q[frt];++frt;
for(int k=head[now];k>-1;k=nex[k])if(c[k^1]&&dist[p[k]]>dist[now]-cc[k]){
//首先c[k^1]是为什么呢，因为我们要保证正流，但是SPFA是倒着跑的，所以说我们要求c[k]的对应反向边是正的，这样保证走的方向是正确的
dist[p[k]]=dist[now]-cc[k];
//因为已经是倒着的了，我们也可以很清楚明白地知道建边的时候反向边的边权是负的，所以减一下就对了（负负得正）
if(!vis[p[k]]){
vis[p[k]]=1;
q[bk++]=p[k];
}
}
vis[now]=0;
}
return dist[s]<1e9;
//判断起点终点是否连通
}
inline int dfs(int x,int low){
//这里就是进行増广了
if(x==t){vis[t]=1;return low;}
int used=0,a;vis[x]=1;
//这边是不是和dinic很像啊
for(int k=head[x];k>-1;k=nex[k])if(!vis[p[k]]&&c[k]&&dist[x]-cc[k]==dist[p[k]]){
//这个条件就表示这条边可以进行増广
a=dfs(p[k],min(c[k],low-used));
if(a)ans+=a*cc[k],c[k]-=a,c[k^1]+=a,used+=a;
//累加答案，加流等操作都在这了
if(used==low)break;
}
return used;
}
inline int costflow(){
int flow=0; ans=0;
while(spfa(s,t)){
//判断起点终点是否连通，不连通说明满流，做完了退出
vis[t]=1;
while(vis[t]){
memset(vis,0,sizeof vis);
flow+=dfs(s,1e9);
//一直増广直到走不到为止（这样也可以省时间哦）
}
}
return flow == dw ? -ans : -1;//这里返回的是最大流，费用的答案在ans里
}
}
int main() {
using namespace ZKW;
freopen("bounce.in", "r", stdin);
freopen("bounce.out", "w", stdout);
int T;
read(T);
while(T--) {
memset(nex,-1,sizeof(nex));
memset(head,-1,sizeof(head));
memset(ban, 0, sizeof(ban));
nedge = -1, dcnt = 0;
read(n), read(m), dw = n * m;
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j < m; ++j)
read(C[i][j]);
for(register int i = 1; i < n; ++i)
for(register int j = 1; j <= m; ++j)
read(R[i][j]);
read(K);
for(register int i = 1; i <= K; ++i) {
read(u), read(v);
ban[u][v] = 1;
}
s = ++dcnt, t = ++dcnt;
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j) {
ND[i][j][Lf] = ++dcnt;
ND[i][j][Rt] = ++dcnt;
adde(s, ND[i][j][Lf], 1, 0);
if(!ban[i][j]) adde(ND[i][j][Lf], ND[i][j][Rt], 1, 0);
adde(ND[i][j][Rt], t, 1, 0);
}
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j) {
if((i + j) & 1) { //横进竖出
if(j < m) adde(ND[i][j + 1][Lf], ND[i][j][Rt], 1, -C[i][j]);
if(j > 1) adde(ND[i][j - 1][Lf], ND[i][j][Rt], 1, -C[i][j - 1]);
if(i < n) adde(ND[i][j][Lf], ND[i + 1][j][Rt], 1, -R[i][j]);
if(i > 1) adde(ND[i][j][Lf], ND[i - 1][j][Rt], 1, -R[i - 1][j]);
} else { //竖进横出
if(j < m) adde(ND[i][j][Lf], ND[i][j + 1][Rt], 1, -C[i][j]);
if(j > 1) adde(ND[i][j][Lf], ND[i][j - 1][Rt], 1, -C[i][j - 1]);
if(i < n) adde(ND[i + 1][j][Lf], ND[i][j][Rt], 1, -R[i][j]);
if(i > 1) adde(ND[i - 1][j][Lf], ND[i][j][Rt], 1, -R[i - 1][j]);
}
}
int ans = costflow();
if(ans == -1) printf("Impossible\n");
else printf("%d\n", ans);
}
return 0;
}
没有帐号? 立即注册