(中等) HDU 3416 Marriage Match IV，SPFA+SAP。
DescriptionDo 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==lowcost+cost 的边留下，然后再求最大流就好了。。。。。。
代码如下：
#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;
int head,Ecou;
int vis;
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.to=v;
E.cost=c;
E.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=0;
que.push(start);
vis=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>lowcost+c)
{
lowcost=lowcost+c;
if(!vis)
{
que.push(v);
vis=1;
}
}
}
}
}
}
namespace second
{
struct Edge
{
int to,next,cap,flow;
};
Edge E;
int Ecou,head;
int gap,dis,pre,cur;
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.to=v;
E.cap=c;
E.flow=0;
E.next=head;
head=Ecou++;
E.to=u;
E.cap=rc;
E.flow=0;
E.next=head;
head=Ecou++;
}
void update(int remm)
{
int u=T;
while(u!=S)
{
E].flow+=remm;
E^1].flow-=remm;
u=E^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=-1;
gap=N;
while(dis<N)
{
loop:
for(int i=cur;i!=-1;i=E.next)
{
v=E.to;
if(E.cap-E.flow && dis==dis+1)
{
pre=i;
cur=i;
u=v;
if(u==T)
{
for(int i=pre;i!=-1;i=pre.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.to])
{
cur=i;
mindis=dis.to];
}
if(--gap]==0)
break;
dis=mindis+1;
++gap];
if(u!=S)
u=E^1].to;
}
return ret;
}
}
int lowcost;
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.to]==lowcost+E.cost)
second::addEdge(u,E.to,1);
}
{
using namespace second;
printf("%d\n",SAP(N));
}
}
return 0;
}
View Code
页:
[1]