(中等) HDU 3416 Marriage Match IV，SPFA+SAP。

659441806

　　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?


　　

　　题意就是求在最短路的基础上有几条路可以到达，但是每条路之间边彼此不能重合。。。

　　然后就是先求出最短路来，然后把所以 lowcost[v]==lowcost+cost[v] 的边留下，然后再求最大流就好了。。。。。。



代码如下：






#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MaxN=5010;
const int MaxM=500005;
const int INF=10e8;
namespace first
{
struct Edge
{
int to,next,cost;
};
Edge E[MaxM];
int head[MaxN],Ecou;
int vis[MaxN];
void init(int N)
{
Ecou=0;
for(int i=1;i<=N;++i)
{
head=-1;
vis=0;
}
}
void addEdge(int u,int v,int c)
{
E[Ecou].to=v;
E[Ecou].cost=c;
E[Ecou].next=head;
head=Ecou++;
}
void SPFA(int lowcost[],int N,int start)
{
queue <int> que;
int u,v,c;
for(int i=1;i<=N;++i)
lowcost=INF;
lowcost[start]=0;
que.push(start);
vis[start]=1;
while(!que.empty())
{
u=que.front();
que.pop();
vis=0;
for(int i=head;i!=-1;i=E.next)
{
v=E.to;
c=E.cost;
if(lowcost[v]>lowcost+c)
{
lowcost[v]=lowcost+c;
if(!vis[v])
{
que.push(v);
vis[v]=1;
}
}
}
}
}
}
namespace second
{
struct Edge
{
int to,next,cap,flow;
};
Edge E[MaxM];
int Ecou,head[MaxN];
int gap[MaxN],dis[MaxN],pre[MaxN],cur[MaxN];
int S,T;
void init(int N,int _S,int _T)
{
S=_S;
T=_T;
Ecou=0;
for(int i=1;i<=N;++i)
{
head=-1;
gap=dis=0;
}
}
void addEdge(int u,int v,int c,int rc=0)
{
E[Ecou].to=v;
E[Ecou].cap=c;
E[Ecou].flow=0;
E[Ecou].next=head;
head=Ecou++;
E[Ecou].to=u;
E[Ecou].cap=rc;
E[Ecou].flow=0;
E[Ecou].next=head[v];
head[v]=Ecou++;
}
void update(int remm)
{
int u=T;
while(u!=S)
{
E[pre].flow+=remm;
E[pre^1].flow-=remm;
u=E[pre^1].to;
}
}
int SAP(int N)
{
for(int i=1;i<=N;++i)
cur=head;
int u,v,ret=0,remm=INF,mindis;
u=S;
pre[S]=-1;
gap[0]=N;
while(dis[S]<N)
{
loop:
for(int i=cur;i!=-1;i=E.next)
{
v=E.to;
if(E.cap-E.flow && dis==dis[v]+1)
{
pre[v]=i;
cur=i;
u=v;
if(u==T)
{
for(int i=pre;i!=-1;i=pre[E[i^1].to])
remm=min(remm,E.cap-E.flow);
ret+=remm;
update(remm);
u=S;
remm=INF;
}
goto loop;
}
}
mindis=N-1;
for(int i=head;i!=-1;i=E.next)
if(E.cap-E.flow && mindis>dis[E.to])
{
cur=i;
mindis=dis[E.to];
}
if(--gap[dis]==0)
break;
dis=mindis+1;
++gap[dis];
if(u!=S)
u=E[pre^1].to;
}
return ret;
}
}
int lowcost[MaxN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int N,M;
int A,B;
int a,b,c;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&N,&M);
first::init(N);
{
using namespace first;
while(M--)
{
scanf("%d %d %d",&a,&b,&c);
addEdge(a,b,c);
}
scanf("%d %d",&A,&B);
SPFA(lowcost,N,A);
second::init(N,A,B);
for(int u=1;u<=N;++u)
for(int i=head;i!=-1;i=E.next)
if(lowcost[E.to]==lowcost+E.cost)
second::addEdge(u,E.to,1);
}
{
using namespace second;
printf("%d\n",SAP(N));
}
}
return 0;
}
View Code