首页 > 代码库 > [USACO 2010 OPEN]SLIED
[USACO 2010 OPEN]SLIED
传送门
某位不愿透露姓名的语文老师说过：
语文学不好将会影响到你各个学科的发展
这道题的题意描述简直有毒。题没看完一眼分层图，然后火速敲了个堆优化的dijkstra，然后就被样例教做人了QAQ
这里说的最坏的情况让我很迷茫？感觉很难判定到底什么是最坏的情况以及确定了最坏的情况应该怎么办....然后我就去扒了扒别人好几年前的代码，耐着性子把pascal的代码看完..恍然大悟..
题目那样描述确实有点不妥当，但是如果说清楚了，那这就成一个完全的裸题了。
要求在最坏的情况下收益最大，假设你现在在一个点上，你已经失误了$i$次，那么还允许你失误$K-i$次，要求最大收益。这里之所以不能采取分层图也是这个原因，到了不同的状态，图的构建方案是不同的。
所以在具体实现时，对于每个状态，需要得到
1.如果不失误，那么到目标状态的最大收益。
2.如果失误，到目标状态的最小收益。
然后对这两个值取$min$,因为题目要求的状况是worst。
1 //oj 1601 2 //by Cydiater 3 //2016.10.6 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <queue> 9 #include <map>10 #include <ctime>11 #include <cmath>12 #include <cstdlib>13 #include <cstdio>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const ll MAXN=2e5+5;20 const ll oo=1000000000000LL;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll N,M,K,LINK[MAXN],len=0,f[MAXN][15];28 struct edge{29 ll y,next,v;30 }e[MAXN];31 bool vis[MAXN];32 namespace solution{33 inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}34 void init(){35 N=read();M=read();K=read();36 up(i,1,M){37 ll x=read(),y=read(),v=read();38 insert(x,y,v);39 }40 }41 void dfs(int node,int fa){42 if(vis[node])return;43 for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa)dfs(e[i].y,node);44 up(j,0,K){45 for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa)46 f[node][j]=max(f[node][j],f[e[i].y][j]+e[i].v);47 if(j<K)for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa)48 f[node][j]=min(f[node][j],f[e[i].y][j+1]+e[i].v);49 f[node][j]=max(f[node][j],0LL);50 }51 vis[node]=1;52 }53 void slove(){54 up(i,1,N)up(j,0,K)f[i][j]=-oo;55 memset(vis,0,sizeof(vis));56 dfs(1,0);57 }58 void output(){59 cout<<f[1][0]<<endl;60 }61 }62 int main(){63 //freopen("input.in","r",stdin);64 using namespace solution;65 init();66 slove();67 output();68 return 0;69 }
[USACO 2010 OPEN]SLIED
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。