365体育网址赛车大赛的赛场由N颗行星和M条双向星际航路构成。驾驶的赛车名也惊世骇俗电驴。

星际竞速

1927: [Sdoi2010]星际竞速

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

【问题讲述】

Description

  10年就的银河系赛车大赛以如起了。作为全银河最盛大的倒有,夺得这个路之冠军的是多丁的
望,来自杰森所α星的减缓也是里有。赛车大赛的赛场由N颗行星以及M条双向星际航路构成,其中每颗行星都
出一个例外之引力值。大赛要求驾驶员们从同颗与这N颗行星之间从来不其它航路的天体出发,访问这N颗行星每粒恰好
一样浅,首先形成这无异于靶的食指获得胜利。由于赛制非常开放,很多人口开着奇妙的自制赛车来参赛。这次悠悠
驾驶的赛车名也惊世骇俗电驴,这是同等管凝聚了都银河最尖端科技结晶的梦乡赛车。作为最高科技的结局,超能电驴有
零星种运动模式:高速航行模式与力爆发模式。在速航行模式下,超能电驴会展开反物质引擎,以数倍于光速的
速沿星际航路高速航行。在力量爆发模式下,超能电驴脱离时空的牢笼,使用超能力进行空中跳跃——在经过同
段时间之稳定后,它能够转走至任意一个行星。天未遂人愿,在比赛的前天,超能电驴在一如既往摆离子风暴中莫
幸好受损,机能出现了有的障碍:在用便捷航行模式之早晚,只能出于每个星球飞往引力比它好的星球,否则赛车就
见面发生爆炸。尽管心爱之跑车出了问题,但是迟迟仍然坚信自己得获大胜。他找到了都银河最明白的贤者——
公,请而吧他配置等同长比赛之方案,使得他能用最为少之光阴得比赛。

  10年已经的银河系赛车大赛以比方起来了。作为全银河最严肃的移动有,夺得这个类型之冠军的是诸多人数的要,来自杰森幢α星的慢性也是其中之一。赛车大赛的赛场由N颗行星与M条双向星际航路构成,其中每颗行星都出一个见仁见智的引力值。大赛要求的哥们于平发与这N颗行星之间没有其他航路的天体出发,访问这N颗行星每粒恰好同一不成,首先形成这等同对象的口获得胜利。由于赛制非常开放,很多总人口开着奇异的自制赛车来参赛。这次悠悠驾驶之跑车名也惊世骇俗电驴,这是一致总理凝聚了全银河最尖端科技结晶的梦赛车。作为高科技的产物,超能电驴有少栽运动模式:高速航行模式和能力爆发模式。在飞航行模式下,超能电驴会展开反物质引擎,以数倍增于光速的速度沿星际航路高速航行。在能力爆发模式下,超能电驴脱离时空之约束,使用超能力进行空中跳跃——在经过一段时间的原则性后,它亦可瞬间活动及任意一个行星。天不遂人愿,在比的前天,超能电驴在一如既往摆离子风暴中不幸受损,机能出现了有些阻力:在动用速航行模式之时光,只能由每个星球飞往引力比它可怜之星球,否则赛车就会见发生爆炸。尽管心爱的跑车出了问题,但是迟迟仍然坚信自己好取得制胜。他找到了净银河最明白的贤者——你,请而吧外配置等同长达比赛之方案,使得他能用最为少之光阴得比赛。

Input

  第一履是片只刚整数N,M。第二行N个数A1~AN,其中Ai表示以能力爆发模式到行星i所待的恒时间。接下
来M行,每行3个正整数ui,vi,wi,表示以编号也ui和vi的行星之间在一样漫长需要航行wi时间的星际航路。输入数据
已经按引力值排序,也就是编号小之行星引力值一定小,且无见面来三三两两颗行星引力值相同。

【输入格式】

Output

  仅含一个正要整数,表示完成比赛所需要的起码时。

  第一履是少单正整数N,M。第二行N个数A1~AN,其中Ai表示以力量爆发模式到行星i所欲的一定时间。接下来M行,每行3个正整数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

  仅含一个恰好整数,表示完成比赛所欲的足足时。

HINT

 

  说明:先以力量爆发模式及行星1,花费时间1。然后切换到便捷航行模式,航行至行星2,花费时间10。之

后连续航行到行星3形成比赛,花费时间1。虽然看起从行星1届行星3再次至行星2重新优良,但咱可非可知那么做,因

为那会造成超能电驴爆炸。N≤800,M≤15000。输入数据被的其他数还未会见超过106。输入数据保证自由两发行星

里及多有同样条航路,且无会见存在某颗行星到祥和之航程。

 

【样例输入】

Source

第一轮Day2

 

拆点

  S与各一个右部点连边,费用为稳定费用,容量也1;

  S与每个左部点之间连边,费用为0,容量也1;

  被拆点之间连边,费用为0,容量也1,可以抵达的左部点连到右部点上,容量也1,费用吗行程长;

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

如此拆点,边容量还是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,花费时间1。然后切换至高速航行模式,航行到行星2,花费时间10。之后继续航行至行星3完成比赛,花费时间1。虽然看起从行星1顶行星3复到行星2复完美,但咱倒无克那么做,因为那会促成超能电驴爆炸。N≤800,M≤15000。输入数据被之其他数还无见面跳106。输入数据保证自由两发行星中至多存在同样长达航线,且非会见是某颗行星到温馨的航道。


题解:

题意就是请刚好拜访各国一个沾的卓绝小时间(费用)

那么把各国一个拆成稀个点,一个相符,一个来

将当下片独点连一长长的下界上界均为 1
的底限,表示正拜访这个点同样糟

剩余的以题意连边

本着,就是一个生上下界无源汇可行最小费用循环流

  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 }

 

相关文章