菜鸟物流的运输网络(计蒜客复赛F)

菜鸟物流有自己的运输网络，网络中包含 nn 个城市物流集散中心，和 mm 对城市之间的运输线路（线路是双向的）。菜鸟物流允许淘宝卖家自行确定包裹的运输路径，但只有一条限制规则：不允许经过重复的城市。淘宝卖家小明从 aa城市寄出快递后，希望包裹在 midmid 城市进行包装加工以后再寄往 bb 城市。

现在小明希望算出一个满足他需求的合法运输路径，你可以帮他算出来么？

已知这样的方案一定存在。请为小明输出任意一个可行方案。

输入格式

第一行一个正整数 T(1 \leq T \leq 10)T(1≤T≤10) 表示数据的组数。

每组数据第一行 22 个正整数 n,m(3 \leq n \leq 100,m \leq \frac{n(n-1)}{2})n,m(3≤n≤100,m≤2n(n−1))，表示城市个数和运输线路数目。

第二行 33 个互不相同正整数 a,b,mid(1 \leq a,b,mid \leq n)a,b,mid(1≤a,b,mid≤n)，表示起点、终点和途径城市。

接下来 mm 行，每行 22 个正整数 x,y(1\leq x,y \leq n)x,y(1≤x,y≤n)，表示每条线路连接的 22个城市。

每组数据一定存在至少一组合法方案。如果有多种满足小明需求的合法运输路径，输出任意一个即可。

输出格式

每组数据输出 LL 个正整数，表示顺次经过的城市的编号，包括起点和终点。每两个整数之间一个空格，最后一个整数后面没有空格。

样例输入

样例输出

1 2 3 4 5
思路：网络流。拆点，以mid为超级源点，流为2，然后在起点和终点加一个超级汇点，然后每个点除了mid都拆成两个点流为1，然后mid拆成流为2的，最后跑Dinic
这样保证了，每个点最多经过一次。然后找路径的话只要从起点和终点，然后找这一个点到其他点流为1的就是这个点的上一个经过的点，因为上个点到这个点的流由一变0，然后反边为1。

  1 #include<stdio.h>

  2 #include<stdlib.h>

  3 #include<algorithm>

  4 #include<iostream>

  5 #include<math.h>

  6 #include<string.h>

  7 #include<vector>

  8 #include<queue>

  9 using namespace std;

 10 int n,m,mid;

 11 struct node

 12 {

 13     int to;

 14     int cap;

 15     int rev;

 16 };

 17 int nn,mm;

 18 vector<node>vec[1000];

 19 int level[1000];

 20 int iter[1000];

 21 void add(int from,int to,int cap);

 22 void bfs(int s);

 23 int dfs(int s,int t,int f);

 24 int max_flow(int s,int t);

 25 int vv[1000];

 26 int main(void)

 27 {

 28     int i,j,k;

 29     scanf("%d",&k);

 30     while(k--)

 31     {

 32         for(i=0; i<1000; i++)

 33             vec[i].clear();

 34         scanf("%d %d",&nn,&mm);

 35         scanf("%d %d %d",&n,&m,&mid);

 36         for(i=1; i<=nn; i++)

 37         {

 38             if(i!=mid)

 39             {

 40                 add(i,i+nn,1);

 41             }

 42         }

 43         add(mid,mid+nn,2);

 44         int x,y;

 45         while(mm--)

 46         {

 47

 48             scanf("%d %d",&x,&y);

 49             if(x==n&&y==m||x==m&&y==n)

 50             {

 51                 continue;

 52             }

 53             else

 54             {

 55                 add(x+nn,y,1);

 56                 add(y+nn,x,1);

 57             }

 58         }

 59         add(n+nn,2*nn+1,1);

 60         add(m+nn,2*nn+1,1);

 61         int akk= max_flow(mid,2*nn+1);

 62         int a=n;

 63         int b=m;

 64         int ans[200];

 65         int cnt=0;

 66         memset(vv,0,sizeof(vv));

 67         for(i=1; i<=nn; i++)

 68         {

 69             if(i!=mid)

 70             {  int uu;  for(uu=0; uu<vec[i].size(); uu++)

 71                             {

 72                                 node ad=vec[i][uu];

 73                                 if(ad.cap)

 74                                     break;

 75                             }

 76                             int ak=vec[i][uu].to;

 77                             vv[i]=ak-nn;

 78

 79             }

 80         }

 81         while(a!=mid)

 82         {

 83             printf("%d ",a);

 84             a=vv[a];

 85         }

 86         printf("%d ",mid);

 87         int cc[105];

 88         int ic=0;

 89         while(b!=mid)

 90         {

 91             cc[ic++]=b;

 92             b=vv[b];

 93         }

 94         for(i=ic-1; i>=1; i--)

 95         {

 96             printf("%d ",cc[i]);

 97         }

 98         printf("%d\n",m);

 99     }

100     return 0;

101 }

102 void add(int from,int to,int cap)

103 {

104     node dd;

105     dd.to=to;

106     dd.cap=cap;

107     dd.rev=vec[to].size();

108     vec[from].push_back(dd);

109     dd.to=from;

110     dd.cap=0;

111     dd.rev=vec[from].size()-1;

112     vec[to].push_back(dd);

113 }

114 void bfs(int s)

115 {

116     queue<int>que;

117     memset(level,-1,sizeof(level));

118     level[s]=0;

119     que.push(s);

120     while(!que.empty())

121     {

122         int v=que.front();

123         que.pop();

124         int i;

125         for(i=0; i<vec[v].size(); i++)

126         {

127             node e=vec[v][i];

128             if(level[e.to]==-1&&e.cap>0)

129             {

130                 level[e.to]=level[v]+1;

131                 que.push(e.to);

132             }

133         }

134     }

135 }

136 int dfs(int s,int t,int f)

137 {

138     if(s==t)

139         return f;

140     for(int &i=iter[s]; i<vec[s].size(); i++)

141     {

142         node &e=vec[s][i];

143         if(level[e.to]>level[s]&&e.cap>0)

144         {

145             int r=dfs(e.to,t,min(e.cap,f));

146             if(r>0)

147             {

148                 e.cap-=r;

149                 vec[e.to][e.rev].cap+=r;

150                 return r;

151             }

152         }

153     }

154     return 0;

155 }

156 int max_flow(int s,int t)

157 {

158     int flow=0;

159     for(;;)

160     {

161         bfs(s);

162         if(level[t]<0)

163             return flow;

164         memset(iter,0,sizeof(iter));

165         int f;

166         while((f=dfs(s,t,10))>0)

167         {

168             flow+=f;

169         }

170     }

171 }

巴特西

菜鸟物流的运输网络(计蒜客复赛F)

样例输入

样例输出

最新文章

热门文章