hdu2732 最大流+拆点
WA自动机~ 人气:0题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2732
题目给定一个场景，有n*m个方格，每个方格代表一个柱子，一个柱子可以承受不同次数的跳跃，开始时图中给定一些地方有蜥蜴，并且给定蜥蜴最多跳跃的步长，只要跳到方格之外就能安全，而且每只蜥蜴不能在同一个地方重合，每次蜥蜴跳离一个地方这个地方的柱子就的承受次数就会减一，问最终会有多少只蜥蜴不能跳出迷宫。
这个问题可以这样思考，每次蜥蜴跳出一个位置之后这个位置的“资源”就会减少1，而这个减少之后的“资源”不可以再利用，而且涉及到点之间的转移，这在图论中和最大流很相似，所以我们想到可不可以将点转化成状态，地图中的每一个位置（i,j）（0<=i,j<n）可以通过i*m+j+1转化成[1,n*m]闭区间之内的位置，所以我们可以把这个设为他的id，可以将点位置拆开成两个，一个是id，表示没有转移时的状态，另一个点是id+n*m,表示这个点拆开之后的另一个状态。设置一个超级源和一个超级汇。
转换策略如下：
①、如果一个点位置（i,j）值num大于0，那么可以连边（id,id+n*m,num），表示最多有num次“流”在这个位置转换，num个用完也就代表不能发生转换，也就是这个位置不能站蜥蜴了。
②、如果一个位置通过跳跃d可以到达外围就设置边（id,T,inf）,就是把这个位置和超级汇连接起来，并且不限制从这里通过的蜥蜴的数量。
③、如果一个位置有蜥蜴，我们可以把这个位置和超级源连接在一起，也就是（S,id,1）1表示在这个位置有一只蜥蜴出发。就相当于把蜥蜴放在一个源点，蜥蜴数量便是源点流量。
④、两个位置之间的距离（横纵坐标绝对值之差）如果小于d那就可以转换，注意连的边是（id+n*m,id2,1），因为在他跳出当前位置时必须当前位置的承受容量减一，所以必须重跳完之后的状态转移。
基本思想就是拆点。需要慎重思考转移的方式。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef unsigned int ui;
4 typedef long long ll;
5 typedef unsigned long long ull;
6 #define pf printf
7 #define mem(a,b) memset(a,b,sizeof(a))
8 #define prime1 1e9+7
9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x)
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x7ffffff
20 inline int read(){
21 int ans=0,w=1;
22 char ch=getchar();
23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
25 return ans*w;
26 }
27 const int maxn=1010;
28 const int maxm=100010;
29 struct flow{
30 int s,t;
31 int head[maxn],nxt[maxm],d[maxn],cur[maxn];//cur当前弧优化
32 bool vis[maxn];
33 struct node{
34 int u,v,w;
35 }p[maxm];
36 int e;
37 void init()
38 {
39 e=0;
40 mem(head,-1);
41 mem(nxt,-1);
42 }
43 void addedge(int u,int v,int w)//顺带添加反向边
44 {
45 p[e].u=u;
46 p[e].v=v;
47 p[e].w=w;
48 nxt[e]=head[u];
49 head[u]=e++;
50 p[e].u=v;
51 p[e].v=u;
52 p[e].w=0;
53 nxt[e]=head[v];
54 head[v]=e++;
55 }
56 bool bfs(int src,int sink)//确定bfs序
57 {
58 mem(vis,0);
59 mem(d,0);
60 d[src]=1;
61 vis[src]=1;
62 queue<int> q;
63 q.push(src);
64 while(!q.empty())
65 {
66 int cur=q.front();
67 q.pop();
68 for(int i=head[cur];~i;i=nxt[i])
69 {
70 int v=p[i].v;
71 if(!vis[v]&&p[i].w)//确定这个点没有被标号，并且不是反向边
72 {
73 vis[v]=1;
74 d[v]=d[cur]+1;
75 q.push(v);
76 }
77 }
78 }
79 if(d[sink])return true;
80 return false;
81 }
82 int dfs(int s,int flow)
83 {
84 if(s==t)return flow;
85 int used=0;
86 for(int& i=cur[s];~i;i=nxt[i])
87 {
88 int v=p[i].v,w=p[i].w;
89 if(d[v]==d[s]+1&&w>0)//根据Dinic算法的思想，只能走正向的、bfs序大一的边
90 {
91 int tmp=dfs(v,min(flow-used,w));
92 if(tmp>0)
93 {
94 p[i].w-=tmp;//更新正向边的流量以及反向边的流量，
95 p[i^1].w+=tmp;//正向边是偶数，它对应的反向边就是正向边+1
96 used+=tmp;//从一个点出发最多的流量是flow，用掉的流量需要更新
97 if(used==flow)break;
98 }
99 }
100 }
101 if(!used)d[s]=0;//从该点出发的流不能被使用，所以这个点在这次搜索中被丢弃
102 return used;
103 }
104 int dinic()
105 {
106 int ans=0;
107 while(bfs(s,t))
108 {
109 memcpy(cur,head,sizeof(head));
110 ans+=dfs(s,inf);
111 }
112 return ans;
113 }
114 }a;
115 int d;
116 int t;
117 char s[50];
118 int main()
119 {
120 //freopen("input.txt","r",stdin);
121 //freopen("output.txt","w",stdout);
122 std::ios::sync_with_stdio(false);
123 t=read();
124 int n,m;
125 int kase=0;
126 while(t--)
127 {
128 a.init();
129 int cnt=0;
130 n=read(),d=read();
131 f(i,0,n-1)
132 {
133 scanf(" %s",s);
134 if(i==0)
135 {
136 m=strlen(s);
137 // a.n=2*n*m+2;//最大流中点的数量设置
138 a.s=0;
139 a.t=2*n*m+1;//设置超级源与超级汇
140 }
141 f(j,0,m-1)
142 {
143 int num=s[j]-'0';
144 if(num>0)//将大于零的格子拆开成两个格子，并连线，
145 {
146 int id=i*m+j+1;
147 a.addedge(id,id+n*m,num);
148 if(i-d<0||i+d>=n||j-d<0||j+d>=m)
149 {
150 a.addedge(id+n*m,a.t,inf);//可以到达安全地点，且流的大小不限制
151 }
152 else
153 {
154 f(k,0,n-1)//由于图的大小不大，所以可以枚举每一个位置检查是否可行
155 f(l,0,m-1)
156 {
157 int id2=k*m+l+1;
158 if(id==id2)continue;
159 if(abs(i-k)+abs(j-l)<=d)
160 a.addedge(id+n*m,id2,inf);//从id位置能够跳到id2位置，但是记住一定是在id位置少1之后的结点上
161 }
162 }
163 }
164 }
165 }
166 f(i,0,n-1)
167 {
168 scanf(" %s",s);
169 f(j,0,m-1)
170 {
171 if(s[j]=='L')//记录蜥蜴的数量并与超级源连线，
172 {
173 cnt++;
174 int id=i*m+j+1;
175 a.addedge(a.s,id,1);
176 }
177 }
178 }
179 int ans=cnt-a.dinic();
180 if(ans==0)pf("Case #%d: no lizard was left behind.\n",++kase);
181 else if(ans==1)pf("Case #%d: 1 lizard was left behind.\n",++kase);
182 else pf("Case #%d: %d lizards were left behind.\n",++kase,ans);
183
184 }
185 }
加载全部内容