bzoj2324 [ZJOI2011]营救皮卡丘 费用流。宠物小精灵之服。

 [ZJOI2011]援救皮卡丘

Time Limit: 10 Sec  Memory
Limit: 256 MB
Submit: 2653  Solved: 1101
[Submit][Status][Discuss]

题目链接

到底时范围: 1000ms 内存限制: 65536kB

描述
宠物小精灵是如出一辙总理讲述小智和外的合作皮卡丘一起冒险的故事。

图片 1

一律天,小智和皮卡丘来到了小聪狩猎场,里面有过多珍贵的野生宠物小精灵。小智为想收服其中的部分小精灵。然而,野生的微快并无那么好让降。对于各级一个野生小精灵而言,小智可能要以群独敏感球才会降它,而在降过程中,野生小精灵也会见指向皮卡丘造成一定之加害(从而减少皮卡丘的体力)。当皮卡丘的体力小于等于0时,小智就亟须终止狩猎(因为他需让皮卡丘疗伤),而令皮卡丘体力小于等于0的野生小精灵也未会见吃小智收服。当小智的机灵球用了经常,狩猎为披露收场。

我们如果小智遇到野生小精灵时有半点单选项:收服它,或者去她。如果小智选择了降,那么自然会丢来能够收服该小精灵的精灵球,而皮卡丘也必将会遭遇相应的危害;如果选距离它,那么有些智不会见损失精灵球,皮卡丘也无见面损失体力。

小智的目标有星星点点独:主要目标是降尽可能多的野生小精灵;如果得以降的略快数量同样,小智希望皮卡丘受到的迫害越小(剩余体力越怪),因为她们还要延续冒险。

现行既领略小智的精灵球数量及皮卡丘的启幕体力,已解各一个小精灵需要的用来收服的精灵球数目及其当被降过程被会针对皮卡丘造成的侵害数目。请问,小智该怎么抉择收服哪些小精灵以达到他的对象也?

输入
输入数据的率先履包含三独整数:N(0 < N < 1000),M(0 < M <
500),K(0 < K <
100),分别表示小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
从此的K行,每一行代表一个野生小精灵,包括个别只整数:收服该小精灵需要之精灵球的数量,以及收服过程被对皮卡丘造成的祸害。

输出
输出为同样执,包含两独整数:C,R,分别代表最好多收服C个稍快,以及收服C个稍快时皮卡丘的剩余体力值最多呢R。

样例输入
样例输入1:
10 100 5
7 10
2 40
2 50
1 20
4 20

样例输入2:
10 100 5
8 110
12 10
20 10
5 200
1 110

样例输出
样例输出1:
3 30

样例输出2:
0 100

提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20)
这样小智一共收服了3单稍快,皮卡丘受到了70沾伤害,剩余100-70=30接触体力。所以输出3
30
对样例输入2:小智一个小精灵都没法收服,皮卡丘也未会见收下任何有害,所以输出0
100

 1 #include<iostream>  
 2 #include<cstring>  
 3 #include<cstdio>  
 4 using namespace std;  
 5 int n,m,k,ans,power;  
 6 int r[105],c[105],f[1005][505];  
 7 int main(){  
 8     scanf("%d%d%d",&n,&m,&k);  
 9     for (int i=1;i<=k;++i)  
10       scanf("%d%d",&r[i],&c[i]);  
11     for (int i=1;i<=k;++i)  
12       for (int p=n;p>=r[i];--p)  
13         for (int q=m;q>=c[i];--q)  
14           f[p][q]=max(f[p][q],f[p-r[i]][q-c[i]]+1);  
15     ans=0; power=m;  
16     for (int i=1;i<=m;++i)  
17       if (f[n][i]>ans){  
18         ans=f[n][i]; power=m-i;  
19       }  
20     printf("%d %d",ans,power);  
21 }  

 

分析:

http://blog.csdn.net/c20190101zjx/article/details/52717370

http://www.cnblogs.com/yi-ye-zhi-qiu/p/7586532.html

http://blog.csdn.net/clove\_unique/article/details/50152305

 

Description

皮卡丘被火箭队用邪恶的谋划抢走了!这三独坏家伙还给小智留下了赤果果的寻衅!为了皮卡丘,也为公平,小智与外的恋人等义不容辞的践踏上了营救皮卡丘的征途。

火箭队一共发N个据点,据点之间在M条双向道路。据点各自于1交N标号。小智一行K人从真新镇出发,营救被累死在N号据点的淘气卡丘。为了有利于起见,我们以真新镇视为0哀号据点,一开始K个人且以0号点。

由于火箭队的许多布防,要惦记摧毁K号据点,必须比照顺序先摧毁1到K-1号据点,并且,如果K-1号据点没有为摧毁,由于防御之连锁性,小智一行任何一个丁登以点K,都见面被察觉,并出严重后果。因此,在K-1号据点被摧毁之前,任何人是无能够通过K号据点的。

为简化问题,我们忽略战斗环节,小智一行任何一个口通过K号据点即看K号据点被摧毁。被损毁的据点依然是得吃通过的。

K个口是足以独家行动之,只要有任何一个人数当K-1号据点被损毁下,经过K号据点,K号据点就让损毁了。显然的,只要N号据点被损毁,皮卡丘就得救了。

野外的征途是勿安全之,因此小智一行要在摧毁N号据点救出皮卡丘的同时,使得K个人所经过的征程的长度总和最少。

伸手您帮小智设计一个顶尖级的抢救方案吧!

 

Input

第一尽包含三个刚刚整数N,M,K。表示一共有N+1只据点,分别从0到N编号,以及M条无往无尽。一开始小智一行共K个人均在0号点。 

连片下M行,每行三单非负整数,第i行之平头为Ai,Bi,Li。表示是同样长达由Ai号据点到Bi号据点的长度为Li的道。

Output

仅含一个平头S,为拯救皮卡丘所欲经的卓绝小之道总和。

Sample Input

3 4 2
0 1 1
1 2 1
2 3 100
0 3 1

Sample Output

3
【样例说明】
小智同小霞同前失去营救皮卡丘。在无比精良方案面临,小智先从真新镇前去1哀号点,接着前去2声泪俱下据点。当小智成功摧毁2如泣如诉据点之后,小霞从真新镇出发直接过去3哀号据点,救出皮卡丘。

HINT

 

于100%底数码满足N ≤ 150, M ≤ 20 000, 1 ≤ K ≤ 10, Li ≤ 10 000,
保证小智一行一定能够抢救出皮卡丘。至于缘何K ≤
10,你可当最终在小智的召唤下,小智,小霞,小刚,小建,小遥,小胜,小光,艾莉丝,天桐,还起失去日本游山玩水之黑猫警长,一同前失去乱火箭队。

 

Source

Day2、

 

题解:https://www.cnblogs.com/liu-runda/p/6294382.html

  1 #include<cstring>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<cstdio>
  6 #include<queue>
  7 
  8 #define inf 1000000007
  9 #define M 100007
 10 #define N 307
 11 #define ll long long
 12 using namespace std;
 13 inline int read()
 14 {
 15     int x=0,f=1;char ch=getchar();
 16     while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();}
 17     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 18     return x*f;
 19 }
 20 
 21 int n,m,k,S,T;
 22 int a[N][N];
 23 int cnt=1,hed[N],nxt[M],rea[M],val[M],cost[M];
 24 int dis[N],flag[N];
 25 struct Node
 26 {
 27     int e,fa;
 28     void init(){e=fa=-1;}
 29 }pre[N];
 30 
 31 void Floyd()
 32 {
 33     for (int k=0;k<=n;k++)
 34         for (int i=0;i<=n;i++)
 35             for (int j=0;j<=n;j++)
 36                 if (k<=i||k<=j) a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
 37 }
 38 void add(int u,int v,int x,int y)
 39 {
 40     nxt[++cnt]=hed[u];
 41     hed[u]=cnt;
 42     rea[cnt]=v;
 43     val[cnt]=x;
 44     cost[cnt]=y;
 45 }
 46 bool Spfa()
 47 {
 48     for (int i=0;i<=T;i++)
 49     {
 50         flag[i]=0;
 51         dis[i]=inf;
 52         pre[i].init();
 53     }
 54     dis[S]=0,flag[S]=1;
 55     queue<int>q;q.push(S);
 56     while(!q.empty())
 57     {
 58         int u=q.front();
 59         q.pop();
 60         for (int i=hed[u];i!=-1;i=nxt[i])
 61         {
 62             int v=rea[i],fee=cost[i];
 63             if ((dis[u]+fee<dis[v])&&val[i]>0)
 64             {
 65                 dis[v]=dis[u]+fee;
 66                 pre[v].fa=u,pre[v].e=i;
 67                 if (flag[v]==0)
 68                 {
 69                     flag[v]==1;
 70                     q.push(v);
 71                 }
 72             }
 73         }
 74         flag[u]=0;
 75     }
 76     if (dis[T]!=inf) return 1;
 77     else return 0;
 78 }
 79 void MFMC()
 80 {
 81     int Flow=0,Cost=0;
 82     while (Spfa())
 83     {
 84         int x=inf;
 85         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
 86         {
 87             int e=pre[i].e;
 88             x=min(x,val[e]);
 89         }
 90         Flow+=x,Cost+=x*dis[T];
 91         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
 92         {
 93             int e=pre[i].e;
 94             val[e]-=x,val[e^1]+=x;
 95         }
 96     }
 97     printf("%d\n",Cost);
 98 }
 99 int main()
100 {
101     memset(hed,-1,sizeof(hed));
102     n=read(),m=read(),k=read();
103     for (int i=0;i<=n;i++)
104         for (int j=0;j<=n;j++)
105             a[i][j]=inf;
106     for (int i=1;i<=m;i++)
107     {
108         int u=read(),v=read(),fee=read();
109         a[u][v]=min(a[u][v],fee);
110         a[v][u]=min(a[v][u],fee);
111     }
112     Floyd();
113     S=2*(n+1),T=S+1;
114     for (int i=0;i<n;i++)
115         for (int j=i+1;j<=n;j++)
116             if (a[i][j]!=inf) add(i,j+n+1,1,a[i][j]),add(j+n+1,i,0,-a[i][j]);
117     for (int i=1;i<=n;i++)
118         add(S,i,1,0),add(i,S,0,0);
119     add(S,0,k,0),add(0,S,0,0);
120     for (int i=1;i<=n;i++)
121         add(i+n+1,T,1,0),add(T,i+n+1,0,0);
122     MFMC();
123 }

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图