1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<stack> #include<set> #include<bitset> #include<time.h> #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,l,r) for(int i=l;i>=r;i--) #define link(x) for(edge *j=h[x];j;j=j->next) #define mem(a) memset(a,0,sizeof(a)) #define ll long long #define eps 1e-8 #define succ(x) (1<<x) #define lowbit(x) (x&(-x)) #define sqr(x) ((x)*(x)) #define mid (x+y>>1) #define NM 10005 #define nm 64 #define pi 3.1415926535897931 using namespace std; const ll inf=998244353; ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f*x; }
struct edge{int t,v;edge*next;}e[NM<<1],*h[NM],*o=e; void add(int x,int y,int v){o->t=y;o->v=v;o->next=h[x];h[x]=o++;} int n,m,k,_x,_t,_y,d[NM][nm]; int a[NM],ans,tot; inline void upd(int&x,int y){x=max(x,y);}
int main(){ srand(time(0)); int _=read();while(_--){ n=read();m=read();k=read();ans=0; inc(i,1,n)h[i]=0; o=e; inc(i,1,m){_x=read();_y=read();_t=read();add(_x,_y,_t);add(_y,_x,_t);} tot=succ(k)-1; inc(p,1,200){ inc(i,1,n)a[i]=rand()%k; inc(i,1,n)inc(j,1,tot)d[i][j]=-inf; inc(i,1,n)d[i][succ(a[i])]=0; inc(v,1,tot)inc(i,1,n)if(d[i][v]>=0&&(succ(a[i])&v)) link(i)if((succ(a[j->t])&v)==0) upd(d[j->t][succ(a[j->t])|v],d[i][v]+j->v); inc(i,1,n)ans=max(ans,d[i][tot]); } if(ans==0)puts("impossible");else printf("%d\n",ans); } return 0; }
|