P3376 【模板】网络最大流——————Q - Marriage Match IV（最短路&最大流）
2024-09-01 05:20:51
第一道题是模板题，下面主要是两种模板，但都用的是Dinic算法（第二个题也是）
第一题：
题意就不需要讲了，直接上代码：
vector代码：
1 //invalid types 'int[int]' for array subscript :字母重复定义
2 #include<stdio.h>
3 #include<string.h>
4 #include<iostream>
5 #include<stdlib.h>
6 #include<algorithm>
7 #include<queue>
8 #include<vector>
9 using namespace std;
10 const int N=10050;
11 const int M=100050;
12 const int INF=0x3f3f3f3f;
13 int n,m,a,b,dep[N];
14 struct shudui
15 {
16 int start,value;
17 }str1;
18 vector<shudui>w[N];
19 queue<int>r;
20 bool bfs() //对每个点进行分层
21 {
22 for(int i=1;i<=n;++i) dep[i]=0;
23 while(!r.empty())
24 {
25 r.pop();
26 }
27 r.push(a);
28 dep[a]=1; //从起点开始增广
29 while(!r.empty())
30 {
31 int now=r.front();
32 r.pop();
33 int len=w[now].size();
34 for(int i=0;i<len;++i)
35 {
36 str1=w[now][i];
37 if(str1.value && !dep[str1.start])
38 {
39 dep[str1.start]=dep[now]+1;
40 r.push(str1.start);
41 }
42 }
43 }
44 return dep[b];
45 }
46 int dfs(int now,int aim,int flow)
47 {
48 if(now==aim || (!flow)) return flow;
49 int res=0;
50 int len=w[now].size();
51 for(int i=0;i<len;++i)
52 {
53 str1=w[now][i];
54 if(str1.value && dep[str1.start]==dep[now]+1)
55 {
56 int kk=dfs(str1.start,aim,min(flow,str1.value));
57 res+=kk;
58 flow-=kk;
59 w[now][i].value-=kk; //我突然方法你把vector中的值赋给str1的时候，你对石头人
60 //但是vector中的值仍然没有变
61 int len1=w[str1.start].size();
62 for(int j=0;j<len1;++j)
63 {
64 if(w[str1.start][j].start==now)
65 {
66 w[str1.start][j].value+=kk;
67 break;
68 }
69 }
70 }
71 }
72 return res;
73 }
74 int Dinic()
75 {
76 int ans=0;
77 while(bfs())
78 {
79 //printf("**\n");
80 ans+=dfs(a,b,INF);
81 }
82 return ans;
83 }
84 int main()
85 {
86 scanf("%d%d%d%d",&n,&m,&a,&b);
87 while(m--)
88 {
89 int u,v,ww;
90 scanf("%d%d%d",&u,&v,&ww);
91 str1.start=v;
92 str1.value=ww;
93 w[u].push_back(str1);
94 str1.start=u;
95 str1.value=0; //它的方向边初始化为0
96 w[v].push_back(str1);
97 }
98 //printf("**\n");
99 printf("%d\n",Dinic());
100 return 0;
101 }
链接表：
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 #include<vector>
5 #include<algorithm>
6 #include<iostream>
7 #define N 10050
8 #define M 100050
9 using namespace std;
10 const int INF=0x3f3f3f3f;
11 int n,m,a,b,fir[N],dep[N],cnt=1; //dep是用来存每个点的深度
12 queue<int>r;
13 struct edge
14 {
15 int next,to,val,flag;
16 }q[M<<1],str1; //要记得这里M<<1,我RE了好几次T_T
17 void add_edge(int u,int v,int w) //存边（正、反）
18 {
19 q[cnt].next=fir[u];
20
21 q[cnt].to=v;
22 q[cnt].val=w;
23 q[cnt].flag=cnt+1;
24 fir[u]=cnt++;
25 q[cnt].next=fir[v];
26
27 q[cnt].to=u;
28 q[cnt].val=0; //反向边的值应该设为0
29 q[cnt].flag=cnt-1; //这个flag的作用就是用来快速查找他的反向边
30 //我的上一个代码用vector来查找某个元素的时候太浪费时间了
31 fir[v]=cnt++;
32 }
33 int bfs() //每次先bfs查看有没有增广路
34 {
35 for(int i=1;i<=n;++i) dep[i]=0;
36 while(!r.empty()) r.pop();
37 r.push(a);
38 dep[a]=1;
39 while(!r.empty())
40 {
41 int now=r.front();
42 r.pop();
43 for(int i=fir[now];i;i=q[i].next)
44 {
45 int v=q[i].to;
46 if(q[i].val && !dep[v])
47 {
48 dep[v]=dep[now]+1;
49 r.push(v);
50 }
51 }
52 }
53 return dep[b];
54 }
55 int dfs(int now,int aim,int flow) //用来查找容量
56 {
57 if(now==aim || !flow)
58 {
59 return flow;
60 }
61 int res=0;
62 for(int i=fir[now];i;i=q[i].next)
63 {
64 int v=q[i].to;
65 if(q[i].val && dep[v]==dep[now]+1) //当容量不为0，而且这一个点是他的下一个深度
66 {
67 int kk=dfs(v,aim,min(flow,q[i].val)); //dfs找是否能到终点
68 res+=kk; //最大流增加
69 flow-=kk; //可用流量减少
70 q[i].val-=kk; //正向边减少流量，反向边增加
71 q[q[i].flag].val+=kk;
72 }
73 }
74 return res;
75 }
76 int Dinic()
77 {
78 int ans=0;
79 while(bfs()) //只要有增广路就能增量
80 {
81 //printf("**\n");
82 ans+=dfs(a,b,INF);
83 }
84 return ans;
85 }
86 int main()
87 {
88 memset(fir,0,sizeof(fir));
89 scanf("%d%d%d%d",&n,&m,&a,&b);
90 while(m--)
91 {
92 int u,v,w;
93 scanf("%d%d%d",&u,&v,&w);
94 add_edge(u,v,w);
95 }
96 printf("%d\n",Dinic());
97 return 0;
98 }
Do not sincere non-interference。
Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once.
So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?
Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once.
So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?
InputThe first line is an integer T indicating the case number.(1<=T<=65)
For each case,there are two integer n and m in the first line ( 2<=n<=1000, 0<=m<=100000 ) ,n is the number of the city and m is the number of the roads.
Then follows m line ,each line have three integers a,b,c,(1<=a,b<=n,0<c<=1000)it means there is a road from a to b and it's distance is c, while there may have no road from b to a. There may have a road from a to a,but you can ignore it. If there are two roads from a to b, they are different.
At last is a line with two integer A and B(1<=A,B<=N,A!=B), means the number of city A and city B.
There may be some blank line between each case.OutputOutput a line with a integer, means the chances starvae can get at most.Sample Input
3
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7 6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6 2 2
1 2 1
1 2 2
1 2
Sample Output
2
1
1
网易翻译不用看来，看也看不懂，这道题就是让你去求出来从起点到终点能有几条最短路，那么这道题就采用 最短路&&最大流
最短路：求有几条最短路，那肯定要先用最短路算法求出来最短长度
最大流：最大流是求从起点到终点最大流度，这样我们只需要把每个边得权值设为1，这样一旦一个边走过，那按照最大流这个边就不可以走，就可以把这道题转化为最短路
在确定最短路中的都是那几条边才到的终点，我们可以d[起点]+边长==d[终点] 来判断，只要满足这个就说明最起码这一点是最短的，因为最短路求出来的每一段都是最短的
最大流：https://blog.csdn.net/stevensonson/article/details/79177530
下面上代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 #include<vector>
5 #include<algorithm>
6 #include<iostream>
7 #define N 1050
8 #define M 100050
9 using namespace std;
10 const int INF=0x3f3f3f3f;
11 int n,m,a,b,fir[N],dep[N],cnt,dis[N],d[N];
12 queue<int>r;
13 struct edge
14 {
15 int next,to,val,flag;
16 } q[M<<1],str1;
17 struct shudui1
18 {
19 int start,value;
20 bool operator <(const shudui1 q)const
21 {
22 return value>q.value;
23 }
24 } str11;
25 struct shudui2
26 {
27 int start,value;
28 } str2;
29 vector<shudui2>w[1005];
30 priority_queue<shudui1>t;
31 int bfs() //每次先bfs查看有没有增广路
32 {
33 for(int i=1;i<=n;++i) dep[i]=0;
34 while(!r.empty()) r.pop();
35 r.push(a);
36 dep[a]=1;
37 while(!r.empty())
38 {
39 int now=r.front();
40 r.pop();
41 for(int i=fir[now];i;i=q[i].next)
42 {
43 int v=q[i].to;
44 if(q[i].val && !dep[v])
45 {
46 dep[v]=dep[now]+1;
47 r.push(v);
48 }
49 }
50 }
51 return dep[b];
52 }
53 int dfs(int now,int aim,int flow) //用来查找容量
54 {
55 if(now==aim || !flow)
56 {
57 return flow;
58 }
59 int res=0;
60 for(int i=fir[now];i;i=q[i].next)
61 {
62 int v=q[i].to;
63 if(q[i].val && dep[v]==dep[now]+1) //当容量不为0，而且这一个点是他的下一个深度
64 {
65 int kk=dfs(v,aim,min(flow,q[i].val)); //dfs找是否能到终点
66 res+=kk; //最大流增加
67 flow-=kk; //可用流量减少
68 q[i].val-=kk; //正向边减少流量，反向边增加
69 q[q[i].flag].val+=kk;
70 }
71 }
72 return res;
73 }
74 int Dinic()
75 {
76 int ans=0;
77 while(bfs()) //只要有增广路就能增量
78 {
79 //printf("**\n");
80 ans+=dfs(a,b,INF);
81 }
82 return ans;
83 }
84 void add_edge(int u,int v,int w)
85 {
86 q[cnt].next=fir[u];
87
88 q[cnt].to=v;
89 q[cnt].val=w;
90 q[cnt].flag=cnt+1;
91 fir[u]=cnt++;
92 q[cnt].next=fir[v];
93
94 q[cnt].to=u;
95 q[cnt].val=0;
96 q[cnt].flag=cnt-1;
97 fir[v]=cnt++;
98 }
99 int main()
100 {
101 int tt;
102 scanf("%d",&tt);
103 while(tt--)
104 {
105 cnt=1;
106 memset(fir,0,sizeof(fir));
107 scanf("%d%d",&n,&m);
108 for(int i=1; i<=n; ++i)
109 w[i].clear();
110 while(m--)
111 {
112 int u,v,ww;
113 scanf("%d%d%d",&u,&v,&ww);
114 str2.start=v;
115 str2.value=ww;
116 w[u].push_back(str2);
117 }
118 scanf("%d%d",&a,&b);
119 memset(d,INF,sizeof(d));
120 memset(dis,0,sizeof(dis));
121 str11.start=a;
122 str11.value=0;
123 t.push(str11);
124 d[str11.start]=0;
125 while(!t.empty())
126 {
127 str11=t.top();
128 t.pop();
129 int x=str11.start;
130 if(dis[x]) continue;
131 dis[x]=1;
132 int len=w[x].size();
133 for(int i=0; i<len; ++i)
134 {
135 str2=w[x][i];
136 if(d[str2.start]>d[x]+str2.value)
137 {
138 str11.value=d[str2.start]=d[x]+str2.value;
139 str11.start=str2.start;
140 t.push(str11);
141 }
142 }
143 }
144 // for(int i=1; i<=n; ++i)
145 // printf("%d ",d[i]);
146 // printf("\n");
147 for(int i=1; i<=n; ++i)
148 {
149 int len=w[i].size();
150 for(int j=0; j<len; ++j)
151 {
152 str2=w[i][j];
153 if(d[i]+str2.value==d[str2.start])
154 {
155 //printf("%d%d***\n",i,str2.start);
156 add_edge(i,str2.start,1);
157 }
158 }
159 }
160 printf("%d\n",Dinic());
161 }
162 return 0;
163 }
最新文章
- .NET里简易实现IoC
- cocos2d-x初步了解
- 谈谈黑客攻防技术的成长规律（aullik5）
- read函数返回值始终为1
- OpenGL图元的颜色属性
- SQL 必知必会-- 第1课：数据库基础和什么是SQL
- IT牛人博客
- 在AD09中查找元件和封装
- Chain of Responsibility - 责任链模式
- Robotium第一天：搭建环境测试微信
- 201521044091 《Java学习笔记》 第六周学习总结
- 【POJ3207】Ikki's Story IV - Panda's Trick
- LoadRunner 压力测试使用基础步骤
- python批量下载微信好友头像，微信头像批量下载
- ArcGIS AddIN 10.3项目与10.1项目的相互转换
- 【转】Map 与 Unordered_map
- 任意两点间的最短路问题（Floyd-Warshall算法）
- OpenSSL编程
- C++用法总结
- python基础之1-安装