开车的赛车名字为惊世骇俗电驴,赛车大赛的比赛场面由N颗行星和M条双向星际航行路线构成

星际竞速

1927: [Sdoi2010]星际竞速

Time Limit: 20 Sec  Memory
Limit: 259 MB
Submit: 2040  Solved: 1257
[Submit][Status][Discuss]

【问题讲述】

Description

  拾年已经的银系赛车大赛又要起来了。作为全银河最盛大的运动之1,夺得那么些类别的季军无疑是广大人的
愿意,来自杰森座α星的冉冉也是里面之一。赛车大赛的赛管由N颗行星和M条双向星际航行路线构成,在那之中每颗行星都
有三个不等的重力值。大赛供给的男生从1颗与那N颗行星之间没有其它国航空公司路的自然界出发,访问那N颗行星每颗恰好
一遍,首先形成那一对象的人获得胜利。由于比赛制度万分开放,多数人驾驶着古怪的自制赛车来参加比赛。这一次悠悠
开车的赛车名叫惊世骇俗电驴,那是一部凝聚了全银河最尖端科学技术结晶的迷梦赛车。作为最高科学和技术的产物,超能电驴有
二种运动格局:高速航行格局和技巧产生情势。在飞快航行形式下,超能电驴会打开反物质引擎,以几倍于光速的
进程沿星际航行路线高速航行。在技能产生模式下,超能电驴脱离时空的自律,使用超技巧举办空间跳跃——在通过一
段时日的原则性之后,它能眨眼之间间移动到任意五个行星。天不遂人愿,在较量的头天,超能电驴在一场离子龙卷风中不
幸受损,机能出现了一部分障碍:在利用便捷航行方式的时候,只好由每一种星球飞往重力比它大的星斗,不然赛车就
会发生爆炸。就算心爱的超跑出了难点,不过迟迟依然坚信本身能够博得大捷。他找到了全银河最领会的贤者——
你,请您为他配置一条竞赛的方案,使得她能够用最少的时刻成功竞技。

  10年早就的银系赛车大赛又要起来了。作为全银河最盛大的移动之一,夺得那些类其他季军无疑是众多个人的只求,来自杰森座α星的缓慢也是中间之1。赛车大赛的比赛场地由N颗行星和M条双向星际航行路线构成,其中每颗行星都有2个不1的引力值。大赛须要司机们从一颗与那N颗行星之间一向不此外航行路线的大自然出发,访问那N颗行星每颗恰好2遍,首先产生那1对象的人获得胜利。由于比赛制度卓殊开放,好多个人驾乘着奇异的自制赛车来参赛。此番悠悠开车的跑车名称为惊世骇俗电驴,这是一部凝聚了全银河最尖端科学技术结晶的睡梦赛车。作为最高科学技术的产物,超能电驴有两种运动情势:高速航行格局和力量产生格局。在便捷航行方式下,超能电驴会议及展览开反物质引擎,以好多倍于光速的快慢沿星际航行路线高速航行。在技术发生情势下,超能电驴脱离时间和空间的牢笼,使用超技巧实行空间跳跃——在通过1段时间的固定之后,它能瞬间活动到自由叁个行星。天不遂人愿,在竞赛的后天,超能电驴在一场离子沙暴中不幸受损,机能出现了一些障碍:在动用高效航行方式的时候,只可以由每种星球飞往重力比它大的星斗,不然赛车就会发生爆炸。就算心爱的超跑出了难题,但是迟迟仍旧坚信自个儿能够博得制胜。他找到了全银河最通晓的贤者——你,请您为他配置一条比赛的方案,使得她能够用最少的岁月成功比赛。

Input

  第一行是四个正整数N,M。第2行N个数A壹~AN,在那之中Ai表示使用力量产生格局达到行星i所需的固定时期。接下
来M行,每行3个正整数ui,vi,wi,表示在数码为ui和vi的行星之间存在一条须求航行wi时间的星际航行路线。输入数据
早就按重力值排序,也便是编号小的行星重力值一定小,且不会有两颗行星重力值同样。

【输入格式】

Output

  仅包涵3个正整数,表示达成比赛所需的足足时间。

  第壹行是五个正整数N,M。第3行N个数A①~AN,其中Ai表示使用力量产生格局达到行星i所需的定位时间。接下来M行,每行三个正整数ui,vi,wi,表示在编号为ui和vi的行星之间存在一条要求航行wi时间的星际航行路线。输入数据现已按重力值排序,也正是编号小的行星重力值一定小,且不会有两颗行星引力值一样。

Sample Input

3 3
1 100 100
2 1 10
1 3 1
2 3 1

【输出格式】

Sample Output

12

  仅包蕴2个正整数,表示实现竞技所需的足足时间。

HINT

 

  表达:先选取力量发生情势到行星壹,费用时间1。然后切换来高速航行情势,航行到行星二,耗时十。之

后持续航行到行星3成就比赛,费用时间1。纵然看起来从行星1到行星3再到行星二更优,但大家却不可能那么做,因

为那会促成超能电驴爆炸。N≤800,M≤15000。输入数据中的任何数都不会超过十陆。输入数据保证自由两颗行星

以内至多存在一条航空线,且不会存在某颗行星到自个儿的航程。

 

【样例输入】

Source

第一轮Day2

 

拆点

  S与每叁个右部点连边,花费为一定成本,容积为一;

  S与种种左部点之间连边,成本为0,体积为一;

  被拆点之间连边,开支为0,体量为一,能够达到的左部点连到右部点上,体积为1,开销为行程长度;

  种种右部点与T连边,费用为0,流量为1。

那般拆点,边体量都以壹意味着每种点去且只去二遍。同时也准保须臾移与跑路不争辩。

#include<cstdio>
#include<iostream>
using namespace std;
const int V=805*2;
const int E=15005*2+V*8;
struct edge{int v,cap,cost,next;}e[E];int tot=1,head[V];
int n,m,S,T,dis[V],q[E],pre[V];bool vis[V];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int x,int y,int z,int cost){
    e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
}
inline bool spfa(){
    for(int i=S;i<=T;i++) dis[i]=2e9,vis[i]=0;
    unsigned short h=0,t=1;q[t]=S;dis[S]=0;
    while(h!=t){
        int x=q[++h];vis[x]=0;
        for(int i=head[x];i;i=e[i].next){
            if(e[i].cap&&dis[e[i].v]>dis[x]+e[i].cost){
                dis[e[i].v]=dis[x]+e[i].cost;
                pre[e[i].v]=i;
                if(!vis[e[i].v]){
                    vis[e[i].v]=1;
                    if(dis[e[i].v]<dis[x])
                        q[h--]=e[i].v;
                    else 
                        q[++t]=e[i].v;
                }
            }
        }
    }
    return dis[T]<2e9;
}
inline int augment(){
    int flow=2e9;
    for(int i=T;i!=S;i=e[pre[i]^1].v) flow=min(flow,e[pre[i]].cap);
    for(int i=T;i!=S;i=e[pre[i]^1].v){
        e[pre[i]].cap-=flow;
        e[pre[i]^1].cap+=flow;
    }
    return dis[T]*flow;
}
inline void MCMF(){
    int ans=0;
    while(spfa()) ans+=augment();
    printf("%d\n",ans);
}
inline void init(){
    n=read();m=read();S=0;T=n<<1|1;
    for(int i=1,x;i<=n;i++){
        x=read();
        add(S,i,1,0);
        add(S,i+n,1,x);
        add(i+n,T,1,0);
    }
    for(int i=1,x,y,z;i<=m;i++){
        x=read();y=read();z=read();
        if(x>y) swap(x,y);
        add(x,y+n,1,z);
    }
}
int main(){
    init();
    MCMF();
    return 0;
}

 

3 3
1 100 100

2 1 10
1 3 1
2 3 1

【样例输出】

12

【样例解释】

  表明:先利用力量产生形式到行星一,耗费时间一。然后切换来便捷航行方式,航行到行星二,开销时间十。之后继续航行到行星三完毕竞赛,费用时间一。即便看起来从行星1到行星3再到行星贰更优,但大家却不可能那么做,因为这会导致超能电驴爆炸。N≤800,M≤15000。输入数据中的任何数都不会超过拾6。输入数据保证自由两颗行星之间至多存在一条航行路线,且不会存在某颗行星到自个儿的航空线。


题解:

题意正是求刚好拜访每三个点的微乎其微时间(花费)

那就是说把每3个拆成多少个点,三个入,贰个出

把那八个点连一条下界上界均为 一的边,表示刚好拜访这几个点叁遍

结余的按题意连边

对,就是一个有上下界无源汇可行最小开销循环流

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 inline void Scan(int &x)
  9 {
 10     char c;
 11     while(!isdigit(c = getchar()));
 12     x = c - '0';
 13     while(isdigit(c = getchar())) x = x * 10 + c - '0';
 14 }
 15 const int maxn = 2e3 + 1;
 16 const int maxm = 3e5 + 1;
 17 const int inf = 2e9 + 1;
 18 int n, m;
 19 int ans;
 20 int len, num;
 21 int s, t, cen, nors, nort, sups, supt;
 22 int nex[maxm], fir[maxn], ver[maxm], con[maxm], pri[maxm];
 23 int que[maxm], dis[maxn];
 24 bool vis[maxn];
 25 int du[maxn];
 26 inline void Init()
 27 {
 28     len = 1;
 29     num = n << 1;
 30     cen = ++num;
 31     sups = ++num;
 32     supt = ++num;
 33 }
 34 inline void Ins(int x, int y, int c, int w)
 35 {
 36     nex[++len] = fir[x];
 37     fir[x] = len;
 38     ver[len] = y;
 39     con[len] = c;
 40     pri[len] = w;
 41 }
 42 inline void Add(int x, int y, int c, int w)
 43 {
 44     Ins(x, y, c, w);
 45     Ins(y, x, 0, -w);
 46 }
 47 inline void Put(int x, int y, int l, int r, int w)
 48 {
 49     du[x] -= l, du[y] += l;
 50     if(l == r) return;
 51     Add(x, y, r - l, w);
 52 }
 53 inline bool Spfa()
 54 {
 55     int head = 0, tail = 1;
 56     for(int i = 1; i <= num; ++i)
 57         dis[i] = inf, vis[i] = false;
 58     que[tail] = s;
 59     vis[s] = true;
 60     dis[s] = 0;
 61     while(head < tail)
 62     {
 63         int u = que[++head];
 64         if(head == maxm) head = 0;
 65         for(int i = fir[u]; i; i = nex[i])
 66         {
 67             if(!con[i]) continue;
 68             int v = ver[i];
 69             if(dis[v] > dis[u] + pri[i])
 70             {
 71                 dis[v] = dis[u] + pri[i];
 72                 if(!vis[v])
 73                 {
 74                     vis[v] = true;
 75                     que[++tail] = v;
 76                     if(tail == maxm) tail = 0;
 77                 }
 78             }
 79         }
 80         vis[u] = false;
 81     }
 82     return dis[t] < inf;
 83 }
 84 int Dinic(int u, int flow)
 85 {
 86     vis[u] = true;
 87     if(u == t) return flow;
 88     int gone = 0;
 89     for(int i = fir[u]; i; i = nex[i])
 90     {
 91         if(!con[i]) continue;
 92         int v = ver[i];
 93         if(vis[v] || dis[v] != dis[u] + pri[i]) continue;
 94         int go = Dinic(v, min(con[i], flow - gone));
 95         if(go)
 96         {
 97             con[i] -= go;
 98             con[i ^ 1] += go;
 99             gone += go;
100             ans += go * pri[i];
101             if(gone == flow) break;
102         }
103     }
104     return gone;
105 }
106 inline int Flow(int x, int y)
107 {
108     s = x, t = y;
109     ans = 0;
110     while(Spfa()) Dinic(s, inf);
111     return ans;
112 }
113 int main()
114 {
115     Scan(n), Scan(m);
116     Init();
117     int x, y, v;
118     for(int i = 1; i <= n; ++i)
119     {
120         Scan(v);
121         Add(cen, i, 1, v);
122         Add(i + n, cen, 1, 0);
123         Put(i, i + n, 1, 1, 0);
124     }
125     for(int i = 1; i <= m; ++i)
126     {
127         Scan(x), Scan(y), Scan(v);
128         if(x == y) continue;
129         if(x > y) swap(x, y);
130         Add(x + n, y, 1, v);
131     }
132     for(int i = 1; i <= num; ++i)
133     {
134         if(du[i] > 0) Add(sups, i, du[i], 0);
135         if(du[i] < 0) Add(i, supt, -du[i], 0);
136     }
137     ans = Flow(sups, supt);
138     printf("%d", ans);
139 }

 

相关文章