很套路的一道题,做过无限之环来看这道题还是十分好想的
因为我比较菜,考试的时候就没能想出来。
按照套路,把格子黑白染色,然后考虑图的特点,到一个地方一定拐弯。
并且,对于一条回路来说,正向和反向的贡献都是一样的。
接下来,我们指定黑、白格子的流向,考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了,我们规定黑格子横进竖出,白格子横出竖进。这样我们把问题抽象成一张图,对于每一个格子可以选择从进向自己连边,自己向出连边,相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件,一个点只能经过一条流量,也就是出入度都是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;
- }
没有帐号? 立即注册