【TJOI2013】循环格

Source and Judge

TJOI2013
bzoj3171
luogu3965

Record

1h

Analysis

请先思考后再展开

首先,显然需要一些决策
但好像不是很好贪心
于是自然鹅言想到了网络流(或者费用流)

然后就不会了,主要是不太熟悉
其实很容易发现题目要求的就是,每个点都要在至少一个环中

可以把题目再转化一下:
给每个节点一滴水
如果每个点都能有水过来,并且消耗掉,
那么显然能满足题目的条件

按照这样建图以后,为了追求最小权值,跑费用流,把额外的边设费用1
所谓费用流,前提是最大流,所以一定会把每个点都满足

不过有个小问题,就是可能自己立刻就出去了
所以要拆一下点,分为入x和出y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
const int MAX_N=50;
struct Nod
{
int hou;
int fm;
bool v;
Nod() {hou=0;v=0;}
}p[MAX_N*MAX_N*2];
struct Edge
{
int y,g;
int c,w;
}e[MAX_N*MAX_N*2*10];
int oth(int x) {return (x&1)?(x+1):(x-1);}
int ln=0;
void ins(int x,int y,int c,int w)
{
e[++ln]=(Edge){y,p[x].hou,c,w};p[x].hou=ln;
e[++ln]=(Edge){x,p[y].hou,0,-w};p[y].hou=ln;
}
int ans=0;
int st,ed;
queue<int> q;
int dis[MAX_N*MAX_N*2];
int flow[MAX_N*MAX_N*2];//最短路径到此流量
bool solve()
{
memset(dis,63,sizeof dis);
memset(flow,63,sizeof flow);
dis[st]=0;p[st].v=1;q.push(st);
while(!q.empty())
{
int x=q.front();q.pop();
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]>dis[x]+e[k].w and e[k].c>0)
{
dis[y]=dis[x]+e[k].w;
p[y].fm=k;
flow[y]=mymin(flow[x],e[k].c);
//debug 不能用全局变量flow,因为路径的选择会改变
if(!p[y].v) p[y].v=1,q.push(y);
}
}
p[x].v=0;
}
if(dis[ed]==INF) return 0;
ans+=flow[ed]*dis[ed];
for(int x=ed;x!=st;)
{
int rd=p[x].fm;
e[rd].c-=flow[ed];e[oth(rd)].c+=flow[ed];
x=e[oth(rd)].y;
}
return 1;
}
int r,c;
int calc(int x,int y,int t)
{
if(x==0) x=r;
if(x==r+1) x=1;
if(y==0) y=c;
if(y==c+1) y=1;
return (x-1)*c+y+(t?(r*c):0);
}
//0右 1左 2上 3下
const int tx[4]={0,0,-1,1};
const int ty[4]={1,-1,0,0};
char mp[MAX_N][MAX_N];
void main()
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++) scanf("%s",mp[i]+1);
st=0;ed=2*r*c+1;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
ins(st,calc(i,j,1),1,0);//st=>y
ins(calc(i,j,0),ed,1,0);//x=>ed
int now;
if(mp[i][j]=='R') now=0;
if(mp[i][j]=='L') now=1;
if(mp[i][j]=='U') now=2;
if(mp[i][j]=='D') now=3;
for(int t=0;t<=3;t++)
ins(calc(i,j,1),calc(i+tx[t],j+ty[t],0),1,now!=t);
}
while(solve()) ;
printf("%d",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/ccfc.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%