Marriage Match IV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1536 Accepted Submission(s): 437
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
Author
starvae@HDU
Source
Recommend
lcy
题意:求完全不同的最短路数目;
题解:先SPFA再用处于最短路上的边建图,容量1;
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int EM=2010; const int VM=500010; const int INF=0x3f3f3f3f; struct Edge{ int u,v,nxt; int cap; }edge[VM]; struct node{ int v,w; }; vector<node> vt[1010]; int n,m,cnt,head[VM],vis[VM],dis[VM]; int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM]; void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].cap=0; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; void SPFA(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=INF; queue<int> q; while(!q.empty()) q.pop(); dis[src]=0; vis[src]=1; q.push(src); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=0;i<(int)vt[u].size();i++){ int v=vt[u][i].v; if(dis[v]>dis[u]+vt[u][i].w){ dis[v]=dis[u]+vt[u][i].w; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } int SAP(int n){ int max_flow=0,u=src,v; int id,mindep; aug[src]=INF; pre[src]=-1; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=n; for(int i=0;i<=n;i++) cur[i]=head[i]; // 初始化当前弧为第一条弧 while(dep[src]<n){ int flag=0; if(u==des){ max_flow+=aug[des]; for(v=pre[des];v!=-1;v=pre[v]){ // 路径回溯更新残留网络 id=cur[v]; edge[id].cap-=aug[des]; edge[id^1].cap+=aug[des]; aug[v]-=aug[des]; // 修改可增广量,以后会用到 if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾 u=v; } } for(int i=cur[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; // 从当前弧开始查找允许弧 if(edge[i].cap>0 && dep[u]==dep[v]+1){ // 找到允许弧 flag=1; pre[v]=u; cur[u]=i; aug[v]=min(aug[u],edge[i].cap); u=v; break; } } if(!flag){ if(--gap[dep[u]]==0) /* gap优化,层次树出现断层则结束算法 */ break; mindep=n; cur[u]=head[u]; for(int i=head[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; if(edge[i].cap>0 && dep[v]<mindep){ mindep=dep[v]; cur[u]=i; // 修改标号的同时修改当前弧 } } dep[u]=mindep+1; gap[dep[u]]++; if(u!=src) // 回溯继续寻找允许弧 u=pre[u]; } } return max_flow; } int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ cnt=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) vt[i].clear(); int u,v,w; node tmp; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); if(u==v) continue; tmp.v=v; tmp.w=w; vt[u].push_back(tmp); } scanf("%d%d",&src,&des); SPFA(); for(int i=1;i<=n;i++) for(int j=0;j<(int)vt[i].size();j++) if(dis[vt[i][j].v]==dis[i]+vt[i][j].w) addedge(i,vt[i][j].v,1); printf("%d\n",SAP(n)); } return 0; }
相关推荐
"hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...
- **HDU** 指的是“杭州电子科技大学”(Hangzhou Dianzi University),这所大学在ACM国际大学生程序设计竞赛中有着优异的表现。 - **ACM** 是指“Association for Computing Machinery”,即计算机协会,而在此处...
HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
【田忌赛马】是一道源自古代中国历史的著名策略问题,被转化为计算机科学中的算法题目,出现在HDU(杭州电子科技大学在线评测系统)的3993号问题中。该题目的主要目的是通过编程来解决如何在不确定的对手策略下,...
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...
HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告