QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132488 | #6560. Broken Minimum Spanning Tree | Sorting# | RE | 1ms | 3600kb | C++20 | 2.7kb | 2023-07-30 00:28:57 | 2023-07-30 00:29:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAXN = 3007 ;
int n , m ;
struct edge {
int x , y , len ;
};
edge a[ MAXN ] ;
int srt[ MAXN ] ;
bool opt[ MAXN ] ;
int prv[ MAXN ] , rnk[ MAXN ] ;
int get ( int x ) {
if ( prv[ x ] == -1 ) { return x ; }
int y = get ( prv[ x ] ) ;
prv[ x ] = y ;
return y ;
}
bool unite ( int x , int y ) {
int k1 = get ( x ) , k2 = get ( y ) ;
if ( k1 == k2 ) { return false ; }
if ( rnk[ k1 ] < rnk[ k2 ] ) { swap ( k1 , k2 ) ; }
rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
prv[ k2 ] = k1 ;
return true ;
}
int foo_prv[ MAXN ] , foo_rnk[ MAXN ] ;
void solve ( ) {
cin >> n >> m ;
for ( int i = 1 ; i <= m ; ++ i ) {
cin >> a[ i ].x >> a[ i ].y >> a[ i ].len ;
srt[ i ] = i ;
}
auto cmp = [ & ] ( int x , int y ) {
if ( a[ x ].len != a[ y ].len ) { return ( a[ x ].len < a[ y ].len ) ; }
return ( x < y ) ;
};
sort ( srt + 1 , srt + m + 1 , cmp ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
prv[ i ] = -1 , rnk[ i ] = 0 ;
}
for ( int i = 1 ; i <= m ; ++ i ) {
opt[ srt[ i ] ] = unite ( a[ srt[ i ] ].x , a[ srt[ i ] ].y ) ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
prv[ i ] = -1 , rnk[ i ] = 0 ;
}
vector < pii > ret ;
for ( int i = 1 ; i <= n - 1 ; ++ i ) {
if ( opt[ i ] == true ) { unite ( a[ i ].x , a[ i ].y ) ; }
}
for ( int i = 1 ; i <= n - 1 ; ++ i ) {
if ( opt[ i ] == true ) { continue ; }
for ( int j = 1 ; j <= n ; ++ j ) {
foo_prv[ j ] = prv[ j ] ;
foo_rnk[ j ] = rnk[ j ] ;
}
for ( int j = i + 1 ; j <= n - 1 ; ++ j ) {
unite ( a[ j ].x , a[ j ].y ) ;
}
for ( int j = n ; j <= m ; ++ j ) {
if ( opt[ j ] == true && get ( a[ j ].x ) != get ( a[ j ].y ) ) {
ret.push_back ( { i , j } ) ;
break ;
}
}
for ( int j = 1 ; j <= n ; ++ j ) {
prv[ j ] = foo_prv[ j ] ;
rnk[ j ] = foo_rnk[ j ] ;
}
auto [ x , y ] = ret.back ( ) ;
unite ( x , y ) ;
}
cout << (int)ret.size ( ) << "\n" ;
for ( auto [ x , y ] : ret ) {
cout << x << " " << y << "\n" ;
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
4 4 1 2 10 2 3 3 3 4 1 1 4 4
output:
1 1 4
result:
ok correct!
Test #2:
score: -100
Runtime Error
input:
6 8 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 1 10 1 3 1 4 6 1