首页 > 代码库 > bzoj3380[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一*
bzoj3380[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一*
bzoj3380[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
题意：
给一个无向图，每一条边都有一个阈值，有一些点有草。牛从点1出发，每当它到达有草的点可以选择吃或不吃，如果吃的话体重加1。对于边如果它的阈值小于牛的体重，则此边不可通过。求牛走一圈回到点1的最大体重。有草节点数≤14。点数≤100，边数≤1000。
题解：
f[i][S]表示当前点为i，草状态为S的状态能否达到。具体看代码。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 110 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0;10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12 return f*x;13 }14 struct e{int t,w,n;}es[maxn*20]; int g[maxn],ess;15 void pe(int f,int t,int w){16 es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;17 }18 bool vis[maxn][17000]; int ans,a[17000],n,m,k,b[maxn];19 void dfs(int x,int y){20 if(vis[x][y])return; vis[x][y]=1; if(x==1)ans=max(ans,a[y]);21 if(b[x]&&(y&(1<<(b[x]-1))))dfs(x,y^(1<<(b[x]-1)));22 for(int i=g[x];i;i=es[i].n)if(es[i].w>=a[y])dfs(es[i].t,y);23 }24 int main(){25 n=read(); m=read(); k=read(); inc(i,1,k){int x=read(); b[x]=i;}26 inc(i,1,m){int x=read(),y=read(),z=read(); pe(x,y,z);}27 inc(i,0,(1<<k)-1){inc(j,0,k-1)if(!(i&(1<<j)))a[i]++;} dfs(1,(1<<k)-1); printf("%d",ans); return 0;28 }
20160909
bzoj3380[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。