解析

關(guān)鍵性質(zhì)：三元環(huán)合法等價(jià)于邊權(quán)和模3等于0。

還有一個(gè)常識(shí)：三元環(huán)的級(jí)別是$O(m\sqrt{m})$。
證明：
三個(gè)點(diǎn)度數(shù)都大于 $\sqrt{m}$ 的點(diǎn)不超過(guò)$C_{\sqrt{m}}^3=m\sqrt{m}$ 個(gè)。
如果含有度數(shù)小于$\sqrt{m}$ 的點(diǎn)，考慮從這樣的點(diǎn)伸出去的每條邊，最多和 $\sqrt{m}$ 條邊配對(duì)成環(huán)，所以也不超過(guò) $m\sqrt{m}$ 個(gè)。

所以本題暴力找出所有的三元環(huán)高斯消元就行了，常數(shù)很小。
看題解學(xué)會(huì)了一直因?yàn)閼T性懶得學(xué)的高斯約旦法。

暴力高消確實(shí)挺不容易想到的，總會(huì)往神仙構(gòu)造那邊想。
但第一個(gè)關(guān)鍵性質(zhì)沒(méi)有看出來(lái)不太應(yīng)該。

代碼

//luogu #include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=2e5+100; const int inf=1e9; const int mod=998244353; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m; int id[80][80]; int a[5050][270],num; int ans[270]; void print(int n,int m){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) printf("%d ",a[i][j]);puts("");}puts(""); }signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifint T=read();while(T--){num=0;memset(id,0,sizeof(id));memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();id[x][y]=id[y][x]=i;if(w!=-1){++num;a[num][i]=1;a[num][m+1]=w;} }for(int x=1;x<=n;x++){for(int y=x+1;y<=n;y++){for(int z=y+1;z<=n;z++){if(id[x][y]&&id[y][z]&&id[x][z]){++num;a[num][id[x][y]]=a[num][id[x][z]]=a[num][id[y][z]]=1;a[num][m+1]=0;}}}}//printf("num=%d\n",num);int id=0;//print(num,m+1);for(int i=1;i<=m;i++){int pos=0;for(int j=id+1;j<=num;j++){if(a[j][i]){pos=j;break;}}if(!pos) continue;++id;swap(a[id],a[pos]);if(a[id][i]==2){for(int j=i;j<=m+1;j++) a[id][j]=(3-a[id][j])%3;}for(int j=1;j<=num;j++){if(j!=id&&a[j][i]){//printf("j=%d\n",j);int x=a[j][i];for(int k=i;k<=m+1;k++){a[j][k]=(a[j][k]-x*a[id][k]+6)%3;//printf(" k=%d %d*%d\n",k,a[j][i],a[id][k]);}}}//print(num,m+1);}bool flag=0;for(int i=id+1;i<=num;i++){if(a[i][m+1]){puts("-1");flag=1;break;}}if(flag) continue;for(int i=1;i<=id;i++){for(int p=1;p<=m;p++){if(a[i][p]){ans[p]=a[i][m+1];break;}}}for(int i=1;i<=m;i++) printf("%d ",ans[i]?ans[i]:3);puts("");}return 0; } /* */

總結(jié)

以上是生活随笔為你收集整理的CF1616F Tricolor Triangles（构造、高斯消元）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。