}
totalflow += augflow;
u = src;
}
int i;
for(i = Curhead[u]; i != -1; i = edge[i].next)
if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
Curhead[u] = i;
revpath[edge[i].ver] = edge[i].rev;
u = edge[i].ver;
}
else // no admissible arc, then relabel this vertex
{
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
Curhead[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = edge[revpath[u]].ver; // Backtrack
}
}
return totalflow;
}
int ind[MAXN], outd[MAXN];
int xx[MAXM], yy[MAXM], cc[MAXM];
int main()
{
int T, m;
scanf("%d", &T);
while(T--)
{
init();
memset(outd, 0, sizeof(outd));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &xx[i], &yy[i], &cc[i]);
ind[yy[i]]++;
outd[xx[i]]++;
}
bool flag = true;
for(int i = 1; i <= n; i++)
if((outd[i] - ind[i]) % 2 != 0)
{
flag = false;
break;
}
if(!flag) {printf("impossible\n"); continue;}
int flow = 0;
for(int i = 1; i <= m; i++)
{
if(xx[i] == yy[i] || cc[i]) continue;
add(xx[i] + 1, yy[i] + 1, 1);
}
src = 1, des = n + 2;
for(int i = 1; i <= n; i++)
{ www.2cto.com
int x = abs(outd[i] - ind[i]) / 2;
if(outd[i] > ind[i]) add(src, i + 1, x), flow += x;
else if(ind[i] > outd[i]) add(i + 1, des, x);
}
n = n + 2;
rev_BFS();
if(maxflow() == flow) printf("possible\n");
else printf("impossible\n");
}
return 0;
}
作者：sdj222555