icontofig | 发布于 2019-07-13 19:09:19 | 阅读量 364 | 最短路 二分 离散化 网络流 最大流

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
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 << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
int n,m;
const int maxn = 2e5+25;
const int maxm = 2e5+5;
int h[maxn];
typedef long long ll;
struct edge{
int fr,to,next;
ll cap;
}e[maxm*11];
int cnt = 0;
e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
e[cnt].next = h[u];h[u] = cnt++;
e[cnt].fr = v;e[cnt].to = u;e[cnt].cap = 0;
e[cnt].next = h[v];h[v] = cnt++;
return;
}
struct edge2{
int to,next;
ll dis;
}e2[maxm<<2];
int g[maxn];
int cnt2 = 0;
e2[cnt2].to = v;e2[cnt2].next = g[u];e2[cnt2].dis = d;g[u] = cnt2++;
return;
}
const ll INF = 1e14;
int S,T;
int r;
int cur[maxn],d[maxn];
ll dis[maxn][11];
bool BFS(int s,int t){
queue<int>q;
for(int i = s;i <= t;++i){
d[i] = -1;
}
d[s] = 0;
q.push(s);
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] == -1 && e[i].cap > 0){
d[v] = d[x] + 1;
q.push(v);
}
}
}
return (d[t] != -1);
}
ll DFS(int x,ll a,int t){
if(x == t || a == 0)return a;
ll flow = 0,f;
for(int &i = cur[x];i != -1;i = e[i].next){
int v = e[i].to;
if(d[v] == d[x] + 1 && e[i].cap > 0){
f = min(a - flow,e[i].cap);
f = DFS(v,f,t);
flow += f;
e[i].cap -= f;
e[i^1].cap += f;
if(flow == a)break;
}
}
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,INF,t);
}
return flow;
}
typedef pair<ll,int> P;
priority_queue<P,vector<P>,greater<P> >q;
void dijkstra(int s,int x){
for(int i = 1;i <= n;++i){
dis[i][x] = INF;
}
dis[s][x] = 0;
P now;
now.first = 0;now.second = s;
q.push(now);
while(!q.empty()){
P xx = q.top();
q.pop();
for(int i = g[xx.second];i != -1;i = e2[i].next){
int v = e2[i].to;
if(dis[v][x] > dis[xx.second][x] + e2[i].dis){
dis[v][x] = dis[xx.second][x] + e2[i].dis;
q.push(make_pair(dis[v][x],v));
}
}
}
return;
}
ll p[maxn];
ll o[maxn];
int u,v;
ll w;
int sh[11],ca[11];
ll sum = 0;
ll dd[maxn*11];
bool check(ll x){
for(int i = S;i <= T;++i){
h[i] = -1;
}
cnt = 0;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= r;++j){
if(dis[i][j] <= x){
}
}
}
for(int i = 1;i <= n;++i)
for(int i = 1;i <= r;++i){
}
ll ret = dinic(S,T);
if(ret == sum)return true;
return false;
}
int main(){
n = get_num();
m = get_num();
r = get_num();
memset(g,-1,sizeof(g));
S = 0;
T = n + r + 1;
sum = 0;
for(int i = 1;i <= n;++i){
p[i] = get_num();
sum += p[i];
}
for(int i = 1;i <= m;++i){
u = get_num();
v = get_num();
w = get_num();
}
for(int i = 1;i <= r;++i){
sh[i] = get_num();
ca[i] = get_num();
}
int num = 0;
for(int i = 1;i <= r;++i){
dijkstra(sh[i],i);
for(int j = 1;j <= n;++j){
dd[++num] = dis[j][i];
}
}
sort(dd+1,dd+num+1);
num = unique(dd+1,dd+num+1) - (dd+1);
int l = 0,r = num,mid,ans;
while(l <= r){
mid = (l + r) >> 1;
if(check(dd[mid])){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%I64d\n",dd[ans]);
return 0;
}```

364 人读过

0 条评论