题目

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
/*

*/
const int N(205),M(2005),INF(1e9);
bool ans;
int hd[N],ed[M][3],ee,du[N],pre[N],dep[N],gap[N],now[N],T,n,m,vtx,s,t,all_flow;
std::queue<int> q;

void add_edge(int u,int v,int w){
	// wt("added ",u," to ",v," flow=",w,"\n");
	ed[++ee][0]=hd[u];
	ed[ee][1]=v;
	ed[ee][2]=w;
	hd[u]=ee;
}
void add(int u,int v,int w,int rev_w){
	add_edge(u,v,w);
	add_edge(v,u,rev_w);
}
void bfs(){
	int i,u,v,w;
	memcpy(now+1,hd+1,vtx<<2);
	dep[t]=1;q.push(t);
	while(q.size()){
		u=q.front();q.pop();
		++gap[dep[u]];
		for(i=hd[u];i;i=ed[i][0]){
			v=ed[i][1];w=ed[i^1][2];
			if(w>0&&!dep[v]){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
}
int isap(){
	int i,u,v,w,res,flow(0);
	bfs();
	u=s;
	while(dep[s]&&dep[s]<=vtx){
		if(u==t){
			res=INF;v=t;
			while(v!=s){
				res=std::min(res,ed[pre[v]][2]);
				v=ed[pre[v]^1][1];
			}
			flow+=res;v=t;
			while(v!=s){
				ed[pre[v]][2]-=res;
				ed[pre[v]^1][2]+=res;
				v=ed[pre[v]^1][1];
			}
			u=s;
		}
		for(i=now[u];i;i=ed[i][0]){
			v=ed[i][1];w=ed[i][2];
			if(w>0&&dep[v]==dep[u]-1){
				now[u]=pre[v]=i;
				u=v;goto lb1;
			}
		}
		if(!--gap[dep[u]]){
			break;
		}
		dep[u]=INF;
		for(i=now[u]=hd[u];i;i=ed[i][0]){
			v=ed[i][1];w=ed[i][2];
			if(w>0){
				dep[u]=std::min(dep[u],dep[v]+1);
			}
		}
		if(dep[u]<INF){
			++gap[dep[u]];
		}
		if(u!=s){
			u=ed[pre[u]^1][1];
		}
		lb1:;
	}
	return flow;
}
void clear(int vtx){
	ee=1;all_flow=0;ans=true;
	memset(hd+1,0,vtx<<2);
	memset(du+1,0,vtx<<2);
	memset(dep+1,0,vtx<<2);
	memset(gap+1,0,vtx<<2);
}
int main(){
	int ca,i,u,v,w;
	scanf("%d",&T);
	for(ca=1;ca<=T;++ca){
		scanf("%d%d",&n,&m);
		vtx=n;s=++vtx;t=++vtx;
		clear(vtx);
		for(i=0;i<m;++i){
			scanf("%d%d%d",&u,&v,&w);
			++du[u];--du[v];
			if(w==0){
				add(u,v,1,1);
			}
		}
		for(i=1;i<=n;++i){
			if(du[i]&1){
				ans=false;
				goto lb1;
			}
			if(du[i]>0){
				add(s,i,du[i]>>1,0);
				all_flow+=du[i]>>1;
			}else if(du[i]<0){
				add(i,t,(-du[i])>>1,0);
			}
		}
		ans=(isap()==all_flow);
		lb1:;
		printf(ans?"possible\n":"impossible\n");
	}
	return 0;
}