C - Portals Gym - 102006C (网络流最小割)

题目链接:https://cn.vjudge.net/contest/283918#problem/C

题目大意:T个测试数据,然后给你一个字符串,每一个字符串包括‘s’,‘t’,‘o’,‘#’,‘.’ 。's'代表起点,‘t’代表终点,‘o’代表传送门(传送门之间可以无限次互相到达),‘#’代表墙壁,‘.’代表空的房间,一个人从s开始,只要不是‘#‘,他都可以走进去,然后问你最少填满几个房间,才能使得无论如何s到达不了t,如果不存在正解的话,输出-1.

具体思路:一个搜索题硬生生搞成了网络流?就是拆点限制流量就可以了,注意拆点。对于传送门,我们可以都统一指向一个点,然后再由这个点连向所有的传送门就可以了,这样就不用两重for互相连边了。

AC代码:

  1 #include<iostream>
  2 #include<stack>
  3 #include<queue>
  4 #include<iomanip>
  5 #include<stdio.h>
  6 #include<cstring>
  7 #include<cstring>
  8 #include<cmath>
  9 #include<algorithm>
 10 #include<map>
 11 #include<vector>
 12 using namespace std;
 13 # define ll long long
 14 const int maxn = 5e5+100;
 15 const int inf = 0x3f3f3f3f;
 16 int pprev[maxn];
 17 int head[maxn];
 18 char str[maxn];
 19 int sto[maxn];
 20 struct node
 21 {
 22     int to;
 23     int flow;
 24     int nex;
 25 } edge[maxn<<1];
 26 int num,st,ed,n;
 27 void addedge(int fr,int to,int flow)
 28 {
 29     edge[num].to=to;
 30     edge[num].flow=flow;
 31     edge[num].nex=head[fr];
 32     head[fr]=num++;
 33     edge[num].to=fr;
 34     edge[num].flow=0;
 35     edge[num].nex=head[to];
 36     head[to]=num++;
 37 }
 38 bool bfs()
 39 {
 40    // memset(prev,-1,sizeof(prev));
 41    for(int i=0;i<=2*n+3;i++)pprev[i]=-1;
 42     pprev[st]=1;
 43     queue<int>q;
 44     q.push(st);
 45     while(!q.empty())
 46     {
 47         int top=q.front();
 48         q.pop();
 49         for(int i=head[top]; i!=-1; i=edge[i].nex)
 50         {
 51             int temp=edge[i].to;
 52             if(pprev[temp]==-1&&edge[i].flow>0)
 53             {
 54                 pprev[temp]=pprev[top]+1;
 55                 q.push(temp);
 56             }
 57         }
 58     }
 59     return pprev[ed]!=-1;
 60 }
 61 int dfs(int u,int flow)
 62 {
 63     if(u==ed)
 64         return flow;
 65     int res=0;
 66     for(int i=head[u]; i!=-1; i=edge[i].nex)
 67     {
 68         int t=edge[i].to;
 69         if(pprev[t]==(pprev[u]+1)&&edge[i].flow>0)
 70         {
 71             int temp=dfs(t,min(flow,edge[i].flow));
 72             edge[i].flow-=temp;
 73             edge[i^1].flow+=temp;
 74             res+=temp;
 75             flow-=temp;
 76             if(flow==0)
 77                 break;
 78         }
 79     }
 80     if(res==0)
 81         pprev[u]=-1;
 82     return res;
 83 }
 84 int dinic()
 85 {
 86     int ans=0;
 87     while(bfs())
 88     {
 89         ans+=dfs(st,inf);
 90     }
 91     return ans;
 92 }
 93 int main()
 94 {
 95  //   freopen("portals.in","r",stdin);
 96     int T;
 97     scanf("%d",&T);
 98     while(T--)
 99     {
100         int sum=0;
101         scanf("%d",&n);
102         scanf("%s",str);
103         for(int i=0; i<=2*n+3; i++)
104         {
105             head[i]=-1;
106         }
107         num=0;
108         for(int i=0;i<n;i++){//其实这里起点和终点不拆点也没问题,只不过为了下一个for循环方便连边。
109         if(str[i]=='s')st=i,addedge(i,n+i,inf);
110         if(str[i]=='e')ed=i,addedge(i,i+n,inf);
111         if(str[i]=='.')addedge(i,n+i,1);
112         if(str[i]=='o')addedge(i,n+i,inf);
113         }
114       //  cout<<st<<" "<<ed<<endl;
115         for(int i=0;i<n-1;i++){
116         if(str[i]!='#'&&str[i+1]!='#'){
117         addedge(i+n,i+1,inf);
118         addedge(i+1+n,i,inf);
119         }
120         }
121         //addedge()
122         for(int i=0;i<n;i++){
123         if(str[i]!='o')continue;
124         addedge(i+n,n*2+2,inf);
125         addedge(n*2+3,i,inf);
126         }
127         addedge(n*2+2,n*2+3,inf);
128         int ans=dinic();
129         printf("%d\n",ans==inf?-1:ans);
130     }
131     return 0;
132 }

 

上一篇:【金色】种瓜得瓜,种豆得豆 Gym - 102072H (线段树)


下一篇:Gym .101879 USP Try-outs (寒假自训第七场)