.
题意:无向图。1. 1到n的最短路。2. 最少付出多少代价删边可以使最短路边长。
题解:最短路+最小割。
代码:
#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;
int n,m,num=1,fst[510],dis[510],h[510],s,t,ans=0;
struct edge
{
int x,y,c,d,n;
}e[500000];
vector<int>pre[510];
bool v[510];
void ins(int x,int y,int c,int d)
{
e[++num]={x,y,c,d,fst[x]};
fst[x]=num;
}
inline void dijkstra()
{
for(int i=1;i<=n;i++)
{
v[i]=0;
dis[i]=2147483647;
}
dis[s]=0;
static priority_queue<pa,vector<pa>,greater<pa> >q;
q.push(make_pair(0,s));
while(!q.empty())
{
// print(q);
int x=q.top().second;
q.pop();
if(v[x])
continue;
v[x]=1;
for(int i=fst[x];i;i=e[i].n)
{
int y=e[i].y;
if(dis[y]==dis[x]+e[i].c)
{
pre[y].push_back(i);
}
else if(dis[y]>dis[x]+e[i].c)
{
pre[y].clear();
pre[y].push_back(i);
dis[y]=dis[x]+e[i].c;
q.push(make_pair(dis[y],y));
}
}
}
}
void dfs(int x)
{
if(v[x])
return;
v[x]=1;
for(int i=0;i<pre[x].size();i++)
{
ins(e[pre[x][i]].x,e[pre[x][i]].y,0,e[pre[x][i]].d);
ins(e[pre[x][i]].y,e[pre[x][i]].x,0,0);
dfs(e[pre[x][i]].x);
}
}
bool bh()
{
static queue<int>q;
for(int i=1;i<=n;i++)
h[i]=0;
q.push(s);
h[1]=1;
while(!q.empty())
{
int x=q.front();
for(int i=fst[x];i;i=e[i].n)
{
int y=e[i].y;
if(!h[y]&&e[i].d)
{
h[y]=h[x]+1;
q.push(y);
}
}
q.pop();
}/*
for(int i=1;i<=n;i++)
printf("%d ",h[i]);
puts("");*/
return h[t];
}
int fd(int x,int f)
{
if(x==t)
return f;
int s=0;
for(int i=fst[x];i;i=e[i].n)
{
int y=e[i].y;
if(s<f&&h[y]==h[x]+1&&e[i].d)
{
int t=fd(y,min(f-s,e[i].d));
s+=t;
e[i].d-=t;
e[i^1].d+=t;
}
}
if(s==0)
h[x]=0;
return s;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int x,y,c,d;
scanf("%d%d%d%d",&x,&y,&c,&d);
ins(x,y,c,d);
ins(y,x,c,d);
}
s=1;
t=n;
dijkstra();
for(int i=1;i<=n;i++)
fst[i]=v[i]=0;
int on=num;
dfs(n);/*
for(int i=on+1;i<=num;i++)
printf("%d %d %d\n",e[i].x,e[i].y,e[i].d);*/
while(bh())
ans+=fd(s,1<<30);
printf("%d\n%d",dis[t],ans);
}