题意

给定一张 $2n$ 个点 $m$ 条边的二分图，边有 $0/1$ 的权值，求一个边权异或和为 $1$ 的完美匹配或报告无解。

$n\le 500$，$m\le n^2$。

题解

二分图的最大匹配的一种求解方法就是网络流，源点连所有左部点，右部点连汇点，流量均为 $1$ 然后跑最大流。特别地我们把源点和汇点连出的边的权值都设成 $0$。假设我们跑出了一组完美匹配，如果权值和确实是奇数那直接输出，否则考虑调整。

网络流在跑完后仍然有流量的边会构成残量网络，而这个残量网络上会存在一些环。若我们在这个环上增加 $1$ 的流（同时也给对应的反向边增加流量），就可以在保证是完美匹配的情况下获得另一组匹配。注意到若这个环上的边权异或和为 $1$，那就成功获得了一组与原先完美匹配异或和不同的匹配。

于是我们只需要在残量网络上找异或和为 $1$ 的环即可，在 dfs 过程中维护一个栈，当发现走到了一条返祖边且走过的路径边权异或和为奇数时就找到了环。这里有一个坑：不能只记录某个点是否走过，而要记录当前权值下这个点是否已经被走过。反例就是两个点之间既有 $0$ 权值的边又有 $1$ 权值的边。

时间复杂度 $O(m\sqrt n)$，因为要求最大流。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,inf=0x3f3f3f3f;
int testcase,n,m,S,T;struct Edge{int to,nxt,val,col;}e[(maxn>>1)*(maxn>>1)<<2];int head[maxn],ecnt;
void addEdge(int u,int v,int w,int c){
    e[++ecnt]=Edge{v,head[u],w,c},head[u]=ecnt;
    e[++ecnt]=Edge{u,head[v],0,c},head[v]=ecnt;
}int dis[maxn],cur[maxn];queue<int>q;
bool bfs(){
    for(int i=S;i<=T;i++)dis[i]=inf,cur[i]=head[i];
    dis[S]=0,q.push(S);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u],v;i;i=e[i].nxt){
            if(e[i].val&&dis[v=e[i].to]==inf)
                dis[v]=dis[u]+1,q.push(v);
        }
    }return dis[T]<inf;
}int dfs(int u,int lim){
    if(u==T||lim==0)return lim;
    int res=0;for(int &i=cur[u],v,tmp;lim&&i;i=e[i].nxt)
        if(dis[v=e[i].to]==dis[u]+1&&(tmp=dfs(v,min(lim,e[i].val))))
            res+=tmp,lim-=tmp,e[i].val-=tmp,e[i^1].val+=tmp;
    return res;
}int work(){int res=0;while(bfs())res+=dfs(S,inf);return res;}
unsigned val[maxn];int frm[maxn];bool vis[maxn],used[maxn][2],ok;
int st[maxn],top;
void findcir(int u,unsigned sum,int id){
    if(!ok){
        if(vis[u]){
            if(sum^val[u]){
                frm[u]=id;do e[frm[st[top]]].val--,e[frm[st[top]]^1].val++;while(st[top--]!=u);
                ok=1;
            }return;
        }if(!used[u][sum]){
            val[u]=sum,used[u][sum]=1,frm[u]=id,st[++top]=u,vis[u]=1;
            for(int i=head[u];!ok&&i;i=e[i].nxt)
                if(e[i].val)findcir(e[i].to,sum^e[i].col,i);
            if(!ok)top--,vis[u]=0;
        }
    }
}
int main(){
    for(scanf("%d",&testcase);testcase--;){
        for(int i=S;i<=T;i++)used[i][0]=used[i][1]=vis[i]=head[i]=0;
        ecnt=1,ok=top=0,scanf("%d%d",&n,&m),S=0,T=n<<1|1;
        for(int i=1,u,v,c;i<=m;i++)scanf("%d%d%d",&u,&v,&c),addEdge(u,v,1,c);
        for(int i=1;i<=n;i++)addEdge(S,i,1,0),addEdge(i+n,T,1,0);
        if(work()<n)puts("-1");
        else{
            unsigned now=0;for(int i=1;i<=m;i++)now^=(e[i<<1|1].val&e[i<<1].col);
            if(now){for(int i=S;!ok&&i<=T;i++)if(!used[i][0]&&!used[i][1])findcir(i,0,-1);if(!ok){puts("-1");continue;}}
            for(int i=1;i<=m;i++)if(e[i<<1|1].val)printf("%d ",i);
            putchar('\n');
        }
    }
    return 0;
}
/*
1
3 6
1 4 0
2 5 0
3 6 0
1 5 1
2 6 1
3 4 1
*/