Lunch Time

淩亂°似流年 2021-11-10 12:48 218阅读 0赞

hdu4807:[http://acm.hdu.edu.cn/showproblem.php?pid=4807][http_acm.hdu.edu.cn_showproblem.php_pid_4807]

题意：给你n个点(0--n-1)，点之间是有向边，0号点有k个人，现在0号点的k个人要到n-1号点。每条边有一个容量，就是单位时间内最多允许c个人通过，通过一条边需要一个单位时间，现在问你最后一个到达n-1号点最短的时间是多少。

题解：这题用到网络流。怎么用呢？首先建图，边的容量自然是原来的容量，费用肯定为1.接着，我们可以想。先选一条路径的话，我们肯定选择一条费用最少的，这里就是距离最短的一条，因为，如果选择其他的一条，当那一条到达时，这一条已经到达，不会影响最后一个人的到达，只会贡献人数的减少。所以肯定选择费用最少的一条。然后，直选一条行不?答案是不一定的，因为这一条仅仅是费用最少，但是容量不一定是最大的。当第一个人到达的时候，接下来每一秒都会有y个人到达，y是流量。所以我们遍历下一条，选择下一条的时候，前一条肯要选，因为前一条不会影响这一条，并且会减少人数，提高运输量。所以，我们要遍历所有可行路径。s\[i\]表示到第i条时候第一次可以运输的总人数，则可以退出递推关系系s\[i\]=y\[i\] +(d\[i\]-d\[i-1\])\*sum\[i-1\],y\[i\]表示第i条可行路径的流量，sum\[i-1\]表示前i-1条额流量和,d\[i\]表示第i条路径的费用。然后求费用流的时候更新就可以了。但是还要注意k==0时候要特判。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 #include<algorithm>
      5 #include<queue>
      6 #include<cmath>
      7 #define inf 100000000
      8 using namespace std;
      9 const int E=1000000;
     10 const int N=10002;
     11 struct Node{
     12     int v, cap, cost, next;    //  re记录逆边的下标。
     13 }edge[E];
     14 int n, m;
     15 long long ans,people;
     16 int k, head[N];
     17 int que[N], pre[N], dis[N];
     18 bool vis[N];
     19 void init(){
         //初始化
     20    k=ans=0;
     21    memset(head,-1,sizeof(head));
     22 }
     23 void addEdge(int u, int v, int ca, int co){
     24     edge[k].v = v;
     25     edge[k].cap = ca;
     26     edge[k].cost = co;
     27     edge[k].next = head[u];
     28     head[u] = k ++;
     29     edge[k].v = u;
     30     edge[k].cap = 0;
     31     edge[k].cost = -co;
     32     edge[k].next = head[v];
     33     head[v] = k ++;
     34 }
     35 bool spfa(){                  //  源点为0，汇点为n。
     36     int i;
     37     for(i = 1; i <= n; i ++){
     38         dis[i] = inf;
     39         vis[i] = false;
     40     }
     41     queue<int>Q;
     42     Q.push(1);
     43     dis[1]=0;
     44     vis[1] = true;
     45     while(!Q.empty()){       //  这里最好用队列，有广搜的意思，堆栈像深搜。
     46         int u = Q.front();
     47         Q.pop();
     48         for(i = head[u]; i != -1; i = edge[i].next){
     49             int v = edge[i].v;
     50             if(edge[i].cap && dis[v] > dis[u] + edge[i].cost){
     51                 dis[v] = dis[u] + edge[i].cost;
     52                 pre[v] = i;
     53                 if(!vis[v]){
     54                     vis[v] = true;
     55                    Q.push(v);
     56                 }
     57             }
     58         }
     59         vis[u] = false;
     60     }
     61     if(dis[n] == inf) return false;
     62     return true;
     63 }
     64 int  end(){
     65     int u, p, sum = inf;
     66     for(u = n; u != 1; u = edge[p^1].v){
         //0是超级源点
     67         p = pre[u];
     68         sum = min(sum, edge[p].cap);
     69     }
     70     for(u = n; u != 1; u = edge[p^1].v){
     71         p = pre[u];
     72         edge[p].cap -= sum;
     73         edge[p^1].cap += sum;
     74     }
     75     return sum;
     76 }
     77 int main(){
     78     int t1,t2,t3;
     79    while(~scanf("%d%d%d",&n,&m,&people)&&n>0){
     80         init();//初始化
     81        for(int i=1;i<=m;i++){
     82         scanf("%d%d%d",&t1,&t2,&t3);
     83           t1++;t2++;
     84           addEdge(t1,t2,t3,1);//无向图要建边两次
     85        }
     86        long long s=people,now=0,sum=0;
     87        ans=inf;
     88        while(spfa()){
     89           int y=end();
     90            s-=((long long)dis[n]-now)*sum+y;
     91            if(s<0)s=0;
     92            sum+=y;now=dis[n];
     93            long long temp=(long long)now+(long long)ceil(s*1.0/sum);
     94            if(temp<ans)ans=temp;
     95        }
     96        if(people==0)ans=0;
     97        if(ans==inf)printf("No solution\n");
     98        else
     99        printf("%I64d\n",ans);
    100    }
    101 }

转载于:https://www.cnblogs.com/chujian123/p/3921563.html

[http_acm.hdu.edu.cn_showproblem.php_pid_4807]: http://acm.hdu.edu.cn/showproblem.php?pid=4807
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/668e59fb2a1946f48b650bf56c6436b3.png