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

题目大意

有n个居民点,m条双向有权路径,和s个避难所。每个居民点有pi个居民,每个避难所的容量为Ci。

现在求能够让所有人避难的最少的需要的时间。

题解

我们如果有一个时间,那么我们该如何判断在这个时间内能不能安置所有居民呢?

很简单就能想到,这是一个利用最大流判断是否存在可行流的问题。

建立从源点s到每个居民点的容量为pi的有向边,从每个居民点到每个避难所容量为+∞的有向边,从每个避难所到汇点t容量为ci的有向边。

然后建完图直接跑最大流,判断最大流的流量是否等于所有的居民人数总和即可。

那这个时间我们该如何去求?

答案是可以二分。

二分出一个答案时间,然后检验这个时间下能否将所有人安置好。当然在建立居民点到避难所的有向边的时候应当考虑该居民点到该避难所的时间会不会大于当前给出的答案时间,若是小于等于则加入此边,否则不加入此边。

至于离散化,是一个能够优化常数的做法。就是预处理所有避难所到所有居民点的距离,并且装入一个数组,并对数组从小到大排序。然后直接枚举数组下标获取答案时间。

这样做是正确的,因为最终答案一定是某个居民点到某个避难所的时间,而不会有多余(这是很显然的,请读者思考)。

代码

#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;
void add(int u,int v,ll c){
    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;
void add2(int u,int v,ll d){
    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){
                add(i,n+j,INF);
            }
        }
    }
    for(int i = 1;i <= n;++i)
        add(S,i,p[i]);
    for(int i = 1;i <= r;++i){
        add(n + i,T,ca[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();
        add2(u,v,w);
        add2(v,u,w);
    }
    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;
}



内容更新于: 2019-07-13 19:09:20
链接地址: http://blog.leanote.com/post/icontofig/e6b30008ad99

上一篇: 骑士共存问题 [网络流24题] 二分图最大独立集

下一篇: CSP201903 T2 二十四点 论STL的正确应用

307 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航