Social Monsters (AOJ2605)
典型円環系.
頭0,実装3くらい
dfsで円環を順に見ていけばいい.線分もあるので,線分のnot端からまちがえて始めちゃわないように注意.
なんだかんだ言ってこういうのに30分かけるのはもったいないよなあ でもかかるんじゃ.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef pair<int,int> P; int N,M,K; vector<P> G[2000]; bool vis[2000]; int dp[2001][2][2],ndp[2001][2][2]; //k,prev,fst int NO=-1e9; void dfs(int v,int p,int c){ if(p<0){ rep(i,K+1) ndp[i][0][0]=dp[i][0][0]; rep(i,K) ndp[i+1][1][1]=dp[i][0][0]; }else if(vis[v]){ rep(k,K+1){ rep(prev,2) rep(fst,2){ if(dp[k][prev][fst]==NO) continue; int ad=0; if(fst&&prev) ad=c; if(ad!=NO) chmax(ndp[k][0][0],dp[k][prev][fst]+ad); } } }else{ rep(k,K+1) rep(prev,2) rep(fst,2){ if(dp[k][prev][fst]==NO) continue; rep(pt,2){ int ad=0; if(pt&&prev) ad=c; if(k+pt<=K&&ad!=NO) chmax(ndp[k+pt][pt][fst],dp[k][prev][fst]+ad); } } } rep(i,K+1) rep(j,2) rep(k,2) dp[i][j][k]=ndp[i][j][k],ndp[i][j][k]=NO; if(vis[v]) return; vis[v]=1; int u=-1,nc=0; for(P pi:G[v]) if(pi.fs!=p) u=pi.fs,nc=pi.sc; if(u<0){ rep(k,K+1) rep(a,2) rep(b,2) chmax(dp[k][0][0],dp[k][a][b]); return; } dfs(u,v,nc); } int dfs1(int v,int p,int r){ if(G[v].size()==1) return v; if(v==r&&p>=0) return v; int u; for(P pi:G[v]) if(pi.fs!=p) u=pi.fs; return dfs1(u,v,r); } int st(int v){ if(G[v].size()<=1) return v; return dfs1(v,-1,G[v][0].fs); } int main(){ cin>>N>>M>>K; rep(i,M){ int a,b,c; cin>>a>>b>>c; a--,b--; if(c==0) c=NO; G[a].pb(P(b,c)); G[b].pb(P(a,c)); } rep(i,K+1) rep(j,2) rep(k,2) dp[i][j][k]=ndp[i][j][k]=NO; dp[0][0][0]=0; rep(i,N) if(!vis[i]){ int v=st(i); dfs(v,-1,0); // show(v); // rep(k,K+1) show(dp[k][0][0]); } int ans=dp[K][0][0]; if(ans==NO) puts("Impossible"); else cout<<ans<<endl; }