C

题目链接：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
",ans==inf?-1:ans);
130     }
131     return 0;
132 }