Hdu-4807-lunch time (dichotomy + fee flow, thinking)

Title Link: http://acm.hdu.edu.cn/showproblem.php?pid=4807

Main idea: n points, m sides, k individuals from point 0 to point n-1. The digraph (not mentioned in the title) has a length of 1 for each side, which has the maximum flow capacity. People's speed is 1. Ask everyone to arrive at n-1.

Thought: at the beginning, I thought it was the biggest flow. I wrote a board and found that there was still a speed limit..

Call the length the cost. Run the cost stream once, and record the residual network for each. (it means the number of people who can arrive at different times). Then two minutes.

Control the maximum time consumption. Divide the first time that meets the requirements, and this time is ans.

The condition of dichotomy is that all traffic control consumed before mid in all time will get comprehensive number of people and judge whether the number of people can reach n-1 is more than k.

ACCode:

 // luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
 
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<time.h>
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a)) / / watermark
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=3e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=192600817;
const double EPS=1.0e-8;
const double PI=acos(-1.0);

struct Node1{
    int v,w,cost,nxt;
    Node1(int _v=0,int _w=0,int _cost=0,int _nxt=0){
        v=_v;w=_w;cost=_cost;nxt=_nxt;
    }
};
struct Node2{
    ll cost,flow;
    Node2(ll _cost=0,ll _flow=0){
        cost=_cost;flow=_flow;
    }
};
Node2 Ans[MAXN];
Node1 Edge[MAXN<<2];
int Head[MAXN],Ecnt;
int Pre[MAXN],Dis[MAXN],Flow[MAXN],Last[MAXN];
int Vis[MAXN];
int maxw,Cnt;
int n,m,k,S,T;

void Intt(){
    clean(Head,-1);Ecnt=0;
    maxw=0;Cnt=0;
}
void Add(int u,int v,int w,int cost){
    Edge[Ecnt]=Node1(v,w,cost,Head[u]);
    Head[u]=Ecnt++;
    Edge[Ecnt]=Node1(u,0,-cost,Head[v]);
    Head[v]=Ecnt++;
}
int SPFA(){
    clean(Vis,0);Vis[S]=1;
    clean(Dis,INF32);Dis[S]=0;
    Flow[S]=INF32;Pre[T]=-1;
    queue<int> que;que.push(S);
    while(que.size()){
        int u=que.front();que.pop();
        Vis[u]=0;
        for(int i=Head[u];i+1;i=Edge[i].nxt){
            int temp=Edge[i].v;
            if(Edge[i].w>0&&Dis[temp]>Dis[u]+Edge[i].cost){
                Dis[temp]=Dis[u]+Edge[i].cost;
                Flow[temp]=min(Flow[u],Edge[i].w);
                Last[temp]=i;
                Pre[temp]=u;
                if(Vis[temp]==0){
                    Vis[temp]=1;que.push(temp);
                }
            }
        }
    }return Dis[T]==INF32?0:1;
}
void MCMF(){
    while(SPFA()){
//        cout<<Cnt<<" "<<Dis[T]<<endl;
        int u=T;Cnt++;
        maxw+=Flow[T];
        Ans[Cnt]=Node2(Dis[T],Flow[T]);
        while(u!=S){
            Edge[Last[u]].w-=Flow[T];
            Edge[Last[u]^1].w+=Flow[T];
            u=Pre[u];
        }
    }
}
ll Judge(ll mid){//Spend up to mid time walking 
    ll tot=0;
    for(int i=1;i<=Cnt;++i){
        if(Ans[i].cost<=mid){
            tot+=Ans[i].flow*(mid-Ans[i].cost+1);
        }
    }return tot;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        int a,b,w;Intt();
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&a,&b,&w);
            Add(a,b,w,1);
        }S=0;T=n-1;
        if(k==0){
            printf("0\n");continue;
        }MCMF();
//        cout<<1<<endl;
        if(maxw==0){
            printf("No solution\n");continue;
        }ll l=1,r=1e9,mid;
//        for(int i=1;i<=Cnt;++i){
//            cout<<Ans[i].cost<<" "<<Ans[i].flow<<endl;
//        }
        //The first satisfactory answer.
        while(l<=r){
            mid=(l+r)>>1;
            if(Judge(mid)>=k) r=mid-1;
            else l=mid+1;
        }printf("%d\n",l);
    }
}

At last, I have finished the problem. At the time of the game, I came up and started this way.. In the end, all the teams wrote it out in one team. I've been on the liver for two hours, give up. The face is very dark. But it's a good one.

Tags: PHP network Linker iOS

Posted on Fri, 29 Nov 2019 22:54:27 -0800 by barry_p