~~前排售卖沙华~~
by wyxdrqc @ 2018-08-21 08:47:34
前排资瓷,无人生还!
by Phecda @ 2018-08-21 08:47:38
@[小可爱三岁七](/space/show?uid=62490) 救命啊qwq
by 兮水XiShui丶 @ 2018-08-21 08:47:57
你你你你。。。。嘤@[浅蓝色](/space/show?uid=54226)
by Phecda @ 2018-08-21 08:48:03
@[Kirito_Rivaille](/space/show?uid=54047) 您$markdown$选错语言了吧$qwq$先帮你调一下格式
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 31011
using std::sort;
using std::unique;
using std::lower_bound;
inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
const int N = 105;
const int M = 3005;
int n , m , t , ans = 1;
struct Edge {
int from;
int to;
int data;
int next;
}e[M];
int head[N] , father[N];
int num[M] , ls[M] , cnt , sum;
int cal_num[M] , sign_num;
struct Same {
int left;
int right;
int val;
}s[M];
void add ( int x , int y , int z ) {
e[++t].from = x;
e[t].to = y;
e[t].data = z;
e[t].next = head[x];
head[x]= t;
return;
}
int Find ( int x ) {
if ( x != father[x] )
return Find ( father[x] );
return father[x];
}
void Union ( int x , int y ) {
x = Find ( x ) , y = Find ( y );
father[x] = y;
return;
}
bool Judge ( int x , int y ) {
x = Find ( x ) , y = Find ( y );
if ( x == y )
return true;
else return false;
}
bool cmp ( Edge x , Edge y ) {
return x.data < y.data;
}
void dfs ( int x , int start , int end , int k ) {
if ( start == end ) {
if ( k == s[x].val )
sum++;
return;
}
int l = e[start].from , r = e[start].to;
if ( ! Judge ( l , r ) ) {
int rr = Find ( r ) , ll = Find ( l );
father[rr] = ll;
dfs ( x , start + 1 , end , k + 1 );
father[rr] = rr;
father[ll] = ll;
}
dfs ( x , start + 1 , end , k );
}
int main ( void ) {
n = read () , m = read ();
for ( int i = 1 ; i <= n ; i++ )
father[i] = i;
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
add ( x , y , z );
}
sort ( e + 1 , e + t + 1 , cmp );
int now_used = 0 ;
for ( int i = 1 ; i <= t ; i++ ) {
if ( e[i].data != e[i - 1].data ) {
s[++sign_num].left = i;
s[sign_num - 1].right = i - 1;
}
int l = e[i].from;
int r = e[i].to;
if ( !Judge ( l , r ) ) {
Union ( l , r );
num[++cnt] = e[i].data;
ls[cnt] = num[cnt];
s[sign_num].val++;
now_used++;
}
}
if ( now_used != n - 1 ) {
puts ( "0" );
return 0;
}
s[sign_num].right = m;
// for ( int i = 1 ; i <= sign_num ; i++ )
// std::cout << s[i].left << " " << s[i].right << " "<< s[i].val << std::endl;
for ( int i = 1 ; i <= n ; i++ )
father[i] = i;
for ( int i = 1; i <= sign_num ; i++ ) {
sum = 0;
dfs ( i , s[i].left , s[i].right + 1 , 0 );
ans = ( ans * sum ) % MOD;
for ( int j = s[i].left ; j <= s[i].right ; j++ ) {
int l = e[i].from , r = e[i].to;
if ( !Judge ( l , r ) )
Union ( l , r );
}
}
printf ( "%d\n" , ans );
return 0;
}
```
by 小可爱三岁七 @ 2018-08-21 08:57:33
@[Kirito_Rivaille](/space/show?uid=54047) 噗嗤……你……真是……
by 小可爱三岁七 @ 2018-08-21 09:08:49
@[Kirito_Rivaille](/space/show?uid=54047) 噗嗤……你……真是……
by wyxdrqc @ 2018-08-21 09:09:28
@[Kirito_Rivaille](/space/show?uid=54047) 你在第$121$行干啥呢$qwq$
下面从第$120$开始:
```cpp
/*line:116*/ for ( int i = 1; i <= sign_num ; i++ ) {
/*............*/
/*120*/ for ( int j = s[i].left ; j <= s[i].right ; j++ ) {
int l = e[i].from , r = e[i].to;
if ( !Judge ( l , r ) )
Union ( l , r );
}
}
```
by 小可爱三岁七 @ 2018-08-21 09:11:12
~~原题是无向图吧~~
by wyxdrqc @ 2018-08-21 09:11:40
@[Kirito_Rivaille](/space/show?uid=54047)
$121$行应该改成
```cpp
int l = e[j].from , r = e[j].to;
```
不过话说你解发真的很清奇啊$qwq$
本宝宝差点没看懂$qwq$
by 小可爱三岁七 @ 2018-08-21 09:12:29