首页 > 代码库 > HDU 3416 Marriage Match IV(spfa+最大流)
HDU 3416 Marriage Match IV(spfa+最大流)
题目的大体意思是:给你一些有向边让你求出给出的点s,t之间最短路的条数。
两边spfa从s到t,和从t到s然后求出在最短路上的点建一条容量为1的边,然后求出s到t的最大的流量,就是最短路的数目。
PS:代码写的姿势不够优美。
Marriage Match IV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2051 Accepted Submission(s): 608
Problem Description
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?
Input
The 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.
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.
Output
Output 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
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <iomanip> #include <stdio.h> #include <string> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> #define eps 1e-12 ///#define M 1000100 #define LL __int64 ///#define LL long long ///#define INF 0x7ffffff #define INF 0x3ffffff #define PI 3.1415926535898 #define zero(x) ((fabs(x)<eps)?0:x) using namespace std; const int maxn = 2010; int cnt; int n, m; int cur[maxn], head[maxn]; int dis[maxn], gap[maxn]; int aug[maxn], pre[maxn]; struct node { int v, w; int next; } f[510000]; int head1[maxn]; int head2[maxn]; int cnt1; int cnt2; struct node1 { int u, v, w; int next; }; node1 pp[500010], ff[500010]; void init() { cnt = 0; cnt1 = 0; cnt2 = 0; memset(head1, -1, sizeof(head1)); memset(head, -1, sizeof(head)); memset(head2, -1, sizeof(head2)); } void add1(int u, int v, int w) { pp[cnt1].u = u; pp[cnt1].v = v; pp[cnt1].w = w; pp[cnt1].next = head1[u]; head1[u] = cnt1++; } void add2(int u, int v, int w) { ff[cnt2].u = u; ff[cnt2].v = v; ff[cnt2].w = w; ff[cnt2].next = head2[u]; head2[u] = cnt2++; } void add(int u, int v, int w) { f[cnt].v = v; f[cnt].w = w; f[cnt].next = head[u]; head[u] = cnt++; f[cnt].v = u; f[cnt].w = 0; f[cnt].next = head[v]; head[v] = cnt++; } int SAP(int s, int e, int n) { int max_flow = 0, v, u = s; int id, mindis; aug[s] = INF; pre[s] = -1; memset(dis, 0, sizeof(dis)); memset(gap, 0, sizeof(gap)); gap[0] = n; for (int i = 0; i <= n; ++i) cur[i] = head[i];/// 初始化当前弧为第一条弧 while (dis[s] < n) { bool flag = false; if (u == e) { max_flow += aug[e]; for (v = pre[e]; v != -1; v = pre[v]) /// 路径回溯更新残留网络 { id = cur[v]; f[id].w -= aug[e]; f[id^1].w += aug[e]; aug[v] -= aug[e]; /// 修改可增广量,以后会用到 if (f[id].w == 0) u = v; /// 不回退到源点,仅回退到容量为0的弧的弧尾 } } for (id = cur[u]; id != -1; id = f[id].next)/// 从当前弧开始查找允许弧 { v = f[id].v; if (f[id].w > 0 && dis[u] == dis[v] + 1) /// 找到允许弧 { flag = true; pre[v] = u; cur[u] = id; aug[v] = min(aug[u], f[id].w); u = v; break; } } if (flag == false) { if (--gap[dis[u]] == 0) break; ///gap优化,层次树出现断层则结束算法 mindis = n; cur[u] = head[u]; for (id = head[u]; id != -1; id = f[id].next) { v = f[id].v; if (f[id].w > 0 && dis[v] < mindis) { mindis = dis[v]; cur[u] = id; /// 修改标号的同时修改当前弧 } } dis[u] = mindis + 1; gap[dis[u]]++; if (u != s) u = pre[u]; /// 回溯继续寻找允许弧 } } return max_flow; } int d1[maxn]; int vis[maxn]; queue<int>fp; void Spfa1(int s) { for(int i = 0; i <= n; i++) d1[i] = INF; while(!fp.empty()) fp.pop(); memset(vis, 0, sizeof(vis)); vis[s] = 1; fp.push(s); d1[s] = 0; while(!fp.empty()) { int x = fp.front(); vis[x] = 0; fp.pop(); for(int i = head1[x]; i != -1; i = pp[i].next) { int v = pp[i].v; if(d1[v] > d1[x]+pp[i].w) { d1[v] = d1[x]+pp[i].w; if(!vis[v]) { fp.push(v); vis[v] = 1; } } } } } int d2[maxn]; void Spfa2(int s) { for(int i = 0; i <= n; i++) d2[i] = INF; while(!fp.empty()) fp.pop(); memset(vis, 0, sizeof(vis)); vis[s] = 1; fp.push(s); d2[s] = 0; while(!fp.empty()) { int x = fp.front(); fp.pop(); vis[x] = 0; for(int i = head2[x]; i != -1; i = ff[i].next) { int v = ff[i].v; if(d2[v] > d2[x]+ff[i].w) { d2[v] = d2[x]+ff[i].w; if(!vis[v]) { fp.push(v); vis[v] = 1; } } } } } int main() { int K; cin >>K; while(K--) { init(); scanf("%d %d",&n, &m); int x, y; int u, v, w; for(int i = 0; i < m; i++) { scanf("%d %d %d",&u, &v, &w); add1(u, v, w); add2(v, u, w); } scanf("%d %d",&x, &y); Spfa1(x); Spfa2(y); for(int i = 0; i < cnt1; i++) if(d1[pp[i].u]+d2[pp[i].v]+pp[i].w == d1[y]) add(pp[i].u, pp[i].v, 1); int ans = SAP(x, y, n); cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。