NC19874. [AHOI2006]上学路线ROUTE
描述
输入描述
输入文件中第一行有两个正整数N和M，分别表示合肥市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第(i+1)行）用四个正整数描述第i条路线：pi, qi, ti, ci；具体含义见上文描述。
输出描述
输出文件最多有两行。第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。第二行输出一个整数C,表示Ci之和
示例1
输入:
6 7 1 2 1 3 2 6 1 5 1 3 1 1 3 4 1 1 4 6 1 1 5 6 1 2 1 5 1 4
输出:
2 5
C++14(g++5.4) 解法, 执行用时: 226ms, 内存消耗: 4968K, 提交时间: 2020-06-17 12:51:50
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=505;
const int M=124750+10;
const int MAX=1<<30;
int n,m;
int f[N][N];
int mymin (int x,int y){return x<y?x:y;}
int P[M],Q[M],T[M],X[M];
struct qq
{
int x,y,z,last;
}s[M*2*2];int num,last[N];
void init (int x,int y,int z)
{
num++;
s[num].x=x;s[num].y=y;s[num].z=z;
s[num].last=last[x];
last[x]=num;
swap(x,y);z=0;
num++;
s[num].x=x;s[num].y=y;s[num].z=z;
s[num].last=last[x];
last[x]=num;
}
int h[N];
bool bt ()
{
memset(h,-1,sizeof(h));
h[1]=1;
queue<int> q;
q.push(1);
while (!q.empty())
{
int x=q.front();q.pop();
for (int u=last[x];u!=-1;u=s[u].last)
{
int y=s[u].y;
if (h[y]==-1&&s[u].z>0)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[n]!=-1;
}
int dfs (int x,int f)
{
if (x==n) return f;
int s1=0;
for (int u=last[x];u!=-1;u=s[u].last)
{
int y=s[u].y;
if (s[u].z>0&&s1<f&&h[y]==h[x]+1)
{
int lalal=dfs(y,mymin(f-s1,s[u].z));
s1+=lalal;
s[u].z-=lalal;
s[u^1].z+=lalal;
}
}
if (s1==0) h[x]=-1;
return s1;
}
int main()
{
memset(f,63,sizeof(f));
scanf("%d%d",&n,&m);
for (int u=1;u<=n;u++) f[u][u]=0;
for (int u=1;u<=m;u++)
{
scanf("%d%d%d%d",&P[u],&Q[u],&T[u],&X[u]);
f[P[u]][Q[u]]=mymin(f[P[u]][Q[u]],T[u]);
f[Q[u]][P[u]]=f[P[u]][Q[u]];
}
for (int u=1;u<=n;u++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
f[i][j]=mymin(f[i][j],f[i][u]+f[u][j]);
printf("%d\n",f[1][n]);
num=1;memset(last,-1,sizeof(last));
for (int u=1;u<=m;u++)
{
int x=P[u],y=Q[u];
if (f[1][x]+T[u]+f[y][n]==f[1][n])
init(x,y,X[u]);
if (f[1][y]+T[u]+f[x][n]==f[1][n])
init(y,x,X[u]);
}
int ans=0;
while (bt()) ans=ans+dfs(1,MAX);
printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 95ms, 内存消耗: 3988K, 提交时间: 2019-10-31 10:39:16
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
const int N=510,M=250010,inf=0x3f3f3f3f;
int head[N],cnt,dis[N],h[N],dep[N],n;
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
int next,to,w,c;
}e[M];
struct Node{
int next,to,w;
}e2[M];
void add(int x,int y,int w,int c){
e[++cnt].next=head[x],e[cnt].to=y,e[cnt].w=w,e[cnt].c=c,head[x]=cnt;
}
void add2(int x,int y,int w){
e2[++cnt].next=h[x],e2[cnt].to=y,e2[cnt].w=w,h[x]=cnt;
e2[++cnt].next=h[y],e2[cnt].to=x,e2[cnt].w=0,h[y]=cnt;
}
bool bfs(){
queue<int>Q;
memset(dep,0,sizeof dep);
Q.push(1),dep[1]=1;
while(!Q.empty()){
int v=Q.front();Q.pop();
for(int i=h[v];i;i=e2[i].next){
int u=e2[i].to;
if(!dep[u]&&e2[i].w){
dep[u]=dep[v]+1;
if(u==n)return 1;
Q.push(u);
}
}
}
return 0;
}
int dfs(int v,int flow){
if(v==n)return flow;
int k,rest=flow;
for(int i=h[v];i&&rest;i=e2[i].next){
int u=e2[i].to;
if(dep[u]==dep[v]+1&&e2[i].w){
int k=dfs(u,min(rest,e2[i].w));
if(!k)dep[u]=0;
rest-=k,e2[i].w-=k;
if(i%2) e2[i+1].w+=k;
else e2[i-1].w+=k;
}
}
return flow-rest;
}
void dj(){
memset(dis,0x3f,sizeof dis);
dis[1]=0,q.push(make_pair(0,1));
while(!q.empty()){
int v=q.top().second;q.pop();
if(vis[v])continue;
vis[v]=1;
for(int i=head[v];i;i=e[i].next){
int u=e[i].to;
if(dis[u]>dis[v]+e[i].w){
dis[u]=dis[v]+e[i].w;
q.push(make_pair(dis[u],u));
}
}
}
}
int main(){
int m,i,x,y,w,c,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d%d%d",&x,&y,&w,&c);
add(x,y,w,c),add(y,x,w,c);
}
dj();
printf("%d\n",dis[n]);
cnt=0;
for(int i=1;i<=n;++i){
for(int j=head[i];j;j=e[j].next){
int u=e[j].to;
if(dis[u]==dis[i]+e[j].w){
add2(i,u,e[j].c);
}
}
}
while(bfs()){
while(int flow=dfs(1,inf))ans+=flow;
}
printf("%d",ans);
}