icontofig | 发布于 2019-07-23 13:56:02 | 阅读量 501 | 最短路 网络流 最小割

## 代码

```#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
struct edge{
int to,next;
ll cap;
}e[maxn<<2];
int h[maxn];
int cur[maxn];
int cnt;
void init(){
cnt = 0;
memset(h,-1,sizeof(h));
return;
}
e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];h[u] = cnt++;
e[cnt].to = u;e[cnt].cap = 0;e[cnt].next = h[v];h[v] = cnt++;
return;
}
ll d[maxn];
bool BFS(int s,int t){
queue<int>q;
for(int i = s;i <= t;++i){
d[i] = INF;
}
q.push(s);
d[s] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = h[x];i != -1;i = e[i].next){
int v = e[i].to;
if(d[v] == INF && e[i].cap > 0){
d[v] = d[x] + 1;
q.push(v);
}
}
}
return d[t] != INF;
}
ll DFS(int now,int t,ll a){
if(a == 0 || now == t)return a;
ll flow = 0,f;
for(int &i = cur[now];i != -1;i = e[i].next){
int v = e[i].to;
if(d[v] == d[now]+1 && e[i].cap > 0){
f = min(a - flow,e[i].cap);
f = DFS(v,t,f);
flow += f;
e[i].cap -= f;
e[i^1].cap += f;
if(flow == a)return flow;
}
}
return flow;
}
ll dinic(int s,int t){
ll flow = 0;
while(BFS(s,t)){
for(int i = s;i <= t;++i)cur[i] = h[i];
flow += DFS(s,t,INF);
}
return flow;
}
}ans;
struct edge2{
int to,next;
ll dis;
}ed[maxn<<1];
int g[maxn];
int cnt = 0;
ed[cnt].to = v;ed[cnt].dis = d;ed[cnt].next = g[u];g[u] = cnt++;
return;
}
ll dis[maxn];
int vis[maxn];
void SPFA(int s,int t){
for(int i = s;i <= t;++i){
dis[i] = INF;
vis[i] = 0;
}
queue<int>q;
dis[s] = 0;
q.push(s);
vis[s] = 1;
while(!q.empty()){
int now = q.front();
q.pop();
vis[now] = 0;
for(int i = g[now];i != -1;i = ed[i].next){
int v = ed[i].to;
if(dis[v] > dis[now] + ed[i].dis){
dis[v] = dis[now] + ed[i].dis;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
return;
}
void BF(int x){
for(int i = g[x];i != -1;i = ed[i].next){
int v = ed[i].to;
if(dis[v] == dis[x] + ed[i].dis){
}
}
return;
}
int n,m;
int u,v,c;
int main(){
T = get_num();
while(T--){
n = get_num();
m = get_num();
ans.init();
memset(g,-1,sizeof(g));
cnt = 0;
for(int i = 1;i <= m;++i){
u = get_num();
v = get_num();
c = get_num();
}
SPFA(1,n);
for(int i = 1;i < n;++i)
BF(i);
ll sum = ans.dinic(1,n);
printf("%lld\n",sum);
}
return 0;
}```

501 人读过

0 条评论