设从东方到天国的每一个国度的号子挨个为1…N,设从北部到天国的每一个国家的编号挨个为1…N

2055: 84人环游世界

Time Limit: 10 Sec  Memory
Limit: 64 MB

【样例输出】

Description

   
想必大家都看过成龙(英文名:chéng lóng)妹夫的《80天环游世界》,里面的忐忑刺激的交手场合一定给你留给了深入的回忆。以后就有诸如此类

    贰个八十三位的集体,也想来四次环游世界。

    他们打算兵分多路,游遍每壹个国度。

   
因为他们根本分布在东面,所以她们只朝西方进军。设从东方到西天的每贰个国度的编号挨个为1…N。假如第i个人的游览路线为P壹 、P2……Pk(0≤k≤N),则P1<P2<……<Pk。

   
家弦户诵,中国一定美丽,这样在环游世界时就有诸多少人通过中国。大家用三个正整数Vi来讲述2个国家的诱惑程度,Vi值越大表示该国家越有魔力,同时也意味着有且仅

有Vi个人会通过那么些国家。

   
为了节省时间,他们打算通过坐飞机来完结环游世界的任务。同时为了省钱,他们愿意总的机票费最小。

   
明日就要出发了,不过几个人临阵脱逃,最后只剩下了M个人去环游世界。他们想精晓最少的总开支,你能告诉她们呢?

  第③行七个正整数N,M。

Sample Output

27

再从那个点向每1个入点连一条无上界的边

Input

先是行八个正整数N,M。

其次行有N个不当先M正整数,分别表示V1,V2……VN。

接下去有N-1行。第i行有N-i个整数,该行的第j个数表示从第i个国家到第i+j个国家的机票费(即便该值等于-1则象征那五个国家间尚未通航)。

【样例输出】

Output

在第二行输出最少的总费用。

新匍京视频,27

HINT

1<= N < =100 1<= M <= 79

 

题解:

做完上下界可行流和最大不大流还不算完,大家还足以搞上下界开销流。。。。。

大家着想那道题的建模:

由于一起有m个人,所以大家十一分建一个节点S‘,连一条S->S’,上下界为[m,m],花费为0的弧,那样大家就限制了总人口

对于各个国家”有且仅有”的限制,大家把国家拆点为入点i和出点i’,对于国家i连一条i->i’,上下界为[vi,vi],费用为0的弧,那样就可以界定通过那个国度的人头

本来,由于可以在随意一个地方初阶旅行,所以大家还要对于每一个国家i连一条S’->i,上下界为[0,inf],费用为0的弧

同理,由于可以在随意3个地点截至旅行,所以大家还要对于各种国家i连一条i’->T,上下界为[0,inf],费用为0的弧

而对此国家i,j间的机票钱,大家须要连一条i’->j,上下界为[0,inf],费用为val[i][j]的弧

在这么构图之后,大家考虑怎么处理上下界:

还是定义totflow数组表示有个别点的入流量-出流量,那么大家给totflow[i]>0的点连i->tt的边,给totflow[i]<0的点连ss->i的边

然后我们着想,最后的总花费应该是附加流的微乎其微费用最大流+初叶流的残量网络中每条边的剩余流量*边权

由于每条边不是费用为0,就是上下界残量(上界-下界)为0,所以残量网络带来的花销为0

从而我们只要计算附加流的蝇头开销最大流输出即可啦!

代码落成:

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 inline int min(int a,int b){return a<b?a:b;}
 5 inline int max(int a,int b){return a>b?a:b;}
 6 const int N=210,M=40010,inf=0x7fffffff;
 7 struct edge{int zhong,next,val,flow;}s[M];
 8 int n,m,e=1,adj[N],totflow[N];
 9 int S,T,ss,tt,Station;
10 int hd,tl,q[M],ans,dis[N],pre[N];
11 inline void add(int qi,int zhong,int flow,int val)
12 {
13     s[++e].zhong=zhong,s[e].next=adj[qi],adj[qi]=e,
14     s[e].flow=flow,s[e].val=val;
15 }
16 inline void Add(int a,int b,int c,int d)
17     {add(a,b,c,d),add(b,a,0,-d);}
18 bool vis[N];
19 inline int Shoot()
20 {
21     int x=tt,f=inf;
22     while(x!=ss)
23         f=min(f,s[pre[x]].flow),
24         x=s[pre[x]^1].zhong;
25     x=tt;
26     while(x!=ss)
27         s[pre[x]].flow-=f,s[pre[x]^1].flow+=f,
28         x=s[pre[x]^1].zhong;
29     return f;
30 }
31 inline bool spfa()
32 {
33     memset(dis,0x7f,sizeof(dis));
34     memset(vis,0,sizeof(vis));
35     dis[ss]=0,vis[ss]=1,q[hd=tl=1]=ss;
36     register int i,j,x,u;
37     while(hd<=tl)
38         for(x=q[hd++],vis[x]=0,i=adj[x];i;i=s[i].next)
39             if(s[i].flow&&dis[(u=s[i].zhong)]>dis[x]+s[i].val)
40             {
41                 pre[u]=i,dis[u]=dis[x]+s[i].val;
42                 if(!vis[u])q[++tl]=u,vis[u]=1;
43             }
44     if(dis[tt]==dis[0])return 0;
45     ans+=dis[tt]*Shoot();
46     return 1;
47 }
48 int main()
49 {
50     register int i,j,k,val,lim;
51     scanf("%d%d",&n,&m);
52     Station=2*n+1,S=Station+1,T=S+1,ss=T+1,tt=ss+1;
53     totflow[S]-=m,totflow[Station]+=m;
54     for(i=1;i<=n;++i)
55     {
56         scanf("%d",&lim);
57         totflow[i]-=lim,totflow[n+i]+=lim;
58         Add(Station,i,inf,0),Add(n+i,T,inf,0);
59     }
60     for(i=1;i<n;++i)
61         for(j=i+1;j<=n;++j)
62         {
63             scanf("%d",&val);
64             if(val!=-1)Add(i+n,j,inf,val);
65         }
66     for(i=1;i<=T;++i)
67     {
68         if(totflow[i]>0)Add(ss,i,totflow[i],0);
69         if(totflow[i]<0)Add(i,tt,-totflow[i],0);
70     }
71     Add(T,S,inf,0);
72     while(spfa());
73     printf("%d\n",ans);
74 }

 

  想必我们都看过成龙(英文名:chéng lóng)四哥的《80天环游世界》,里面的忐忑不安刺激的格斗场合一定给您留给了长远的映像。将来就有那样1个81人的团队,也想来两次环游世界。

Sample Input

6 3
2 1 3 1 2 1
2 6 8 5 0
8 2 4 1
6 1 0
4 -1
4

1<= N <
=100 1<= M <= 79

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

  第三行有N个不高于M正整数,分别表示V1,V2……VN。

  在第③行输出最少的总开支。

题意是求 m
个人(每一种人早先点任意)通过路径经过第 i 个国家刚刚 v[i]
次的很小费用

二个点向另二个点连上界下界均为
v[i] 的边,其它边下界均为 0


  他们打算兵分多路,游遍每多个国家。

  为了节省时间,他们打算通过坐飞机来成功环游世界的职务。同时为了省钱,他们盼望总的机票费最小。

  因为她们首要分布在东方,所以他们只朝西方进军。设从北边到西天的每三个国家的号码顺序为1…N。倘使第i个人的畅游路线为P1、P2……Pk(0≤k≤N),则P1<P2<……<Pk。

【输出格式】

题解:

其余的根据题意建边

每一个点拆成八个点,3个入,1个出

对于流量为 m
和无限制初始点必要

【输入格式】

大家新建3个点,从顶级源向那一个点连容积为
m 的边

事实上就是在原图中的源点向那些点连下界为
m 的边

6 3
2 1 3 1 2
1
2 6 8 5
0
8 2 4 1
6 1 0
4 -1
4

【样例输入】

考虑有上下界无源汇可行最小花费循环流

八十位环游世界

【难题讲述】

  闻名遐迩,中国非常美丽,那样在环游世界时就有很几人经过中国。大家用三个正整数Vi来描述一个国度的引发程度,Vi值越大表示该国家越有魔力,同时也意味有且仅有Vi个人会经过那3个国家。

  接下去有N-1行。第i行有N-i个整数,该行的第j个数表示从第i个国家到第i+j个国家的机票费(若是该值等于-1则意味着那五个国家间尚未通航)。

  今天将要出发了,不过有个外人临阵脱逃,最后只剩余了M个人去环游世界。他们想知道最少的总费用,你能告诉她们啊?