hdu 3339 In Action 背包+flyod

2019-11-06 07:13:21

字体：大中小

来源：转载

供稿：网友

题目链接:

http://acm.hdu.edu.cn/showPRoblem.php?pid=3339

题意:

给你一个图，每个点都有权值，然后让你派出多辆坦克，破环至少占权值一半的城市，派出坦克的代价就是从0点到那些城市的距离求最少代价

题解:

点数很少，注意有重边跑一发flyod，然后背包dp

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll 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;}//////////////////////////////////////////////////////////////////////////const int maxn = 100+10;int d[maxn][maxn],d1[maxn],dp[11000],power[maxn];int main(){ int T = read(); while(T--){ int n,m;scanf("%d%d",&n,&m); for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) d[i][j] = INF; for(int i=0; i<m; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); d[u][v] = d[v][u] = min(d[u][v],w); } ll aim = 0; for(int i=1; i<=n; i++){ power[i] = read(); aim += power[i]; } for(int k=0; k<=n; k++) for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) d[i][j] = min(d[i][j],d[i][k]+d[k][j]); ll sum = 0; for(int i=0; i<=n; i++) if(d[0][i] < INF) sum += d[0][i]; MS(dp); for(int i=1; i<=n; i++) for(int j=sum; j>=d[0][i]; j--) dp[j] = max(dp[j],dp[j-d[0][i]]+power[i]); ll ans = INF; for(int i=0; i<=sum; i++) if(dp[i]>=(aim/2+1)){ ans = i; break; } if(ans == INF) cout << "impossible/n"; else cout << ans << endl; } return 0;}

上一篇：最小生成树

下一篇：Pomelo+unity3d采坑日志

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注