読者です 読者をやめる 読者になる 読者になる

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;
}