二分答案，2sat判定。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; #define pb(a) push(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c)); } template<class T> T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c)); } void debug() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); //freopen("d:\out1.txt","w",stdout); #endif } int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } const int maxn=205; struct TwoSat { int n; vector<int> g[maxn*2]; bool mark[maxn*2]; int s[maxn*2],c; bool dfs(int x) { if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; s[c++]=x; for(int i=0;i<g[x].size();i++) { if(!dfs(g[x][i]))return false; } return true; } void init(int n) { this->n=n; for(int i=0;i<n*2;i++) g[i].clear(); memset(mark,0,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*2+xval; y=y*2+yval; g[x].push_back(y^1); g[y].push_back(x^1); } bool solve() { for(int i=0;i<n*2;i+=2) { if(!mark[i]&&!mark[i+1]) { c=0; if(!dfs(i)) { while(c>0)mark[s[--c]]=0; if(!dfs(i+1))return false; } } } return true; } }; TwoSat solver; const int maxm=10005; int a[maxm],b[maxm],c[maxm]; int n,m; int check(int k) { solver.init(n); for(int i=0;i<k;i++) { if(c[i]==0) { int x=a[i],y=b[i]; solver.add_clause(x,0,y,0); } if(c[i]==2) { int x=a[i],y=b[i]; solver.add_clause(x,1,y,1); } if(c[i]==1) { int x=a[i],y=b[i]; solver.add_clause(x,0,y,1); solver.add_clause(x,1,y,0); } } return solver.solve(); } int main() { int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); int l=0,r=m+1; while(l<r) { int mid=(r+l)>>1; if(check(mid)) l=mid+1; else r=mid; } printf("%d ",l-1); } return 0; }