Lvat_s Blog

这题有2问

第一问SPFA

第二问先从1->n 求一遍最短路，再从n->1求一遍最短路，然后判定每条边是否可能在最短路上

即D[e[i].a]+Di[e[i].b]+e[i].t==ans

注意每条边的反向边也需要判断一下

然后跑一遍最大流就行了（最小割=最大流）

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int h[505],n,m,en,en1,D[505],Di[505],flag[505],S,T,cur[505];

struct Es{
int a,b,t,c;
}E[200005];

struct Edge1{
int b,v,next;
}e1[300005];

struct Edge{
int b,f,next,back;
}e[300005];

void AddEdge1(int sa,int sb,int sc){
e1[++en1].b=sb;
e1[en1].v=sc;
e1[en1].next=h[sa];
h[sa]=en1;
}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}

int Spfa(int S,int T){
queue<int> Q;
memset(D,127,sizeof(D));
memset(flag,0,sizeof(flag));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e1[i].next){
		int v=e1[i].b;
		if(D[u]+e1[i].v<D[v]){
			D[v]=D[u]+e1[i].v;
            if(!flag[v]){
				Q.push(v);
				flag[v]=1;
            }
		}
	}
}
return D[T];
}

int Spfa2(int S,int T){
queue<int> Q;
memset(Di,127,sizeof(Di));
memset(flag,0,sizeof(flag));
Q.push(S);
Di[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e1[i].next){
		int v=e1[i].b;
		if(Di[u]+e1[i].v<Di[v]){
			Di[v]=Di[u]+e1[i].v;
            if(!flag[v]){
				Q.push(v);
				flag[v]=1;
            }
		}
	}
}
return Di[T];
}

int Bfs(){
queue<int> Q;
Q.push(S);
memset(flag,0,sizeof(flag));
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(flag[v] || !e[i].f)continue;
		flag[v]=flag[u]+1;
		Q.push(v);
	}
}
return flag[T];
}

int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
	if(flag[v]==flag[u]+1 && e[i].f && (fl=Dfs(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f==0)return flow;
	}
}
return flow-f;
}

int Dinic(){
int ans=0;
while(Bfs()){
	for(int i=1;i<=n;i++)cur[i]=h[i];
	ans+=Dfs(S,2100000000);
}
return ans;
}

int main(){
freopen("1266.in","r",stdin);
freopen("1266.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
	scanf("%d %d %d %d",&E[i].a,&E[i].b,&E[i].t,&E[i].c);
	AddEdge1(E[i].a,E[i].b,E[i].t);
	AddEdge1(E[i].b,E[i].a,E[i].t);
}
int ans1=Spfa(1,n),ans2=Spfa2(n,1);
memset(h,0,sizeof(h));
printf("%d\n",ans1);
for(int i=1;i<=m;i++){
	if(D[E[i].a]+Di[E[i].b]+E[i].t==ans1){AddEdge(E[i].a,E[i].b,E[i].c);}
	if(Di[E[i].a]+D[E[i].b]+E[i].t==ans1){AddEdge(E[i].b,E[i].a,E[i].c);}
}
S=1;T=n;
ans2=Dinic();
printf("%d\n",ans2);
return 0;
}