BZOJ 1266: [AHOI2006]上学路线route Floyd_最小割

时间:2022-05-21 08:19:26

十分简单的一道题.
图这么小,跑一边 Floyd 就得到第一问最短路径的答案.
考虑第二问怎么求:
我们可以先将最短路径组成的图从原图中抽离出来,构成新图 $G$.
我们发现,只要 $G$ 的起点与终点联通,那么最短路径就仍然存在.
所以我们想用最小的代价破坏掉 $G$ 点起点与终点的连通性.
这不就是最小割的定义嘛...... 跑一边最大流即可.

Code:

#include <bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 200000
#define N 502
#define ll int
#define inf 1000000
using namespace std;
int n,m;
struct Graph
{
int u,v,dis,c;
Graph(int u = 0,int v = 0,int dis = 0,int c = 0) : u(u), v(v), dis(dis), c(c){}
}G[maxn];
namespace Dinic{
struct Edge
{
int from,to,cap;
Edge(int a = 0,int b = 0,int c = 0):from(a),to(b),cap(c){}
};
vector <Edge> edges;
vector <int> G[N];
queue <int> Q;
int current[N], d[N], vis[N],s,t;
void add(int u,int v,int c)
{
edges.push_back(Edge(u,v,c));
edges.push_back(Edge(v,u,0));
int kk = edges.size();
G[u].push_back(kk - 2);
G[v].push_back(kk - 1);
}
int BFS()
{
memset(vis,0,sizeof(vis));
vis[s] = 1, d[s] = 0;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int sz = G[u].size(),i = 0;i < sz; ++i)
{
Edge e = edges[G[u][i]];
if(e.cap > 0 && !vis[e.to])
{
vis[e.to] = 1, d[e.to] = d[u] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int cur)
{
if(x == t) return cur;
int f=0,flow = 0;
for(int sz = G[x].size(),i = current[x];i < sz; ++i)
{
current[x] = i;
Edge e = edges[G[x][i]];
if(e.cap > 0 && d[e.to] == d[x] + 1)
{
f = dfs(e.to, min(cur,e.cap));
cur -= f, flow += f;
edges[G[x][i]].cap -= f, edges[G[x][i] ^ 1].cap += f;
}
if(cur == 0) break;
}
return flow;
}
int maxflow()
{
int ans = 0;
while(BFS())
{
memset(current,0,sizeof(current));
ans += dfs(s,inf);
}
return ans;
}
};
namespace Floyd{
ll dis[N][N];
void init()
{
for(int i = 0;i < N; ++i)
for(int j = 0;j < N; ++j) dis[i][j] = inf;
for(int i = 0;i < N; ++i) dis[i][i] = 0;
}
void calc()
{
for(int k = 1;k <= n; ++k)
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
for(int i = 1;i <= m; ++i)
{
Graph e = G[i];
if(dis[1][e.u] + dis[e.v][n] + e.dis == dis[1][n]) Dinic :: add(e.u,e.v,e.c);
if(dis[1][e.v] + dis[e.u][n] + e.dis == dis[1][n]) Dinic :: add(e.v,e.u,e.c);
}
}
};
int main()
{
// setIO("input");
Floyd :: init();
scanf("%d%d",&n,&m);
for(int i = 1,a,b,c,d;i <= m; ++i)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
Floyd :: dis[a][b] = Floyd :: dis[b][a] = c;
G[i] = Graph(a,b,c,d);
}
Floyd :: calc();
printf("%d\n",Floyd :: dis[1][n]);
Dinic :: s = 1, Dinic :: t = n;
printf("%d",Dinic :: maxflow());
return 0;
}