#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define MAX_N 1000
using namespace std;
int N, M;
struct S{
int idx, data;
};
struct E{
int x, y, z;
bool operator <(const E &a)const{
return y<a.y;
}
};
vector<E> e;
vector<int> gp[MAX_N+1];
vector<E> gp2[MAX_N+1];
int p[MAX_N+1][15];
int c[MAX_N+1];
int lv[MAX_N+1];
int ans;
int dp[MAX_N+1];
void dfs(int x){
for(int i=1; i<15; i++){
p[x][i] = p[p[x][i-1]][i-1];
}
for(int i=0; i<gp[x].size(); i++){
if(c[gp[x][i]]==0){
c[gp[x][i]] = 3 - c[x];
p[gp[x][i]][0] = x;
lv[gp[x][i]] = lv[x] + 1;
dfs(gp[x][i]);
}
}
}
int up(int x, int y){
int two = (1<<14);
for(int i=14; i>=0; i--){
if(y>=two){
x = p[x][i];
y-=two;
}
two/=2;
}
return x;
}
int lca(int x, int y){
if(lv[x]>lv[y]){
x = up(x, lv[x]-lv[y]);
}
if(lv[x]<lv[y]){
y = up(y, lv[y]-lv[x]);
}
if(x==y) return x;
for(int i=14; i>=0; i--){
if(p[x][i]!=p[y][i]){
x = p[x][i]; y = p[y][i];
}
}
if(x==y) return x;
return p[x][0];
}
void dfs2(int x){
dp[x] = 0;
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]!=p[x][0]){
dfs2(gp[x][i]);
dp[x]+=dp[gp[x][i]];
}
}
for(int i=0; i<gp2[x].size(); i++){
int pp1, pp2;
E now = gp2[x][i];
pp1 = up(now.x, lv[now.x]-lv[x]-1); pp2 = up(now.y, lv[now.y]-lv[x]-1);
if(now.x==x) now.z+=dp[now.y];
else if(now.y==x) now.z+=dp[now.x];
else now.z+=dp[now.x]+dp[now.y];
for(int j=0; j<gp[x].size(); j++){
if(pp1==gp[x][j]) now.x = j;
if(pp2==gp[x][j]) now.y = j;
}
if(pp1==x) now.x = -1;
if(pp2==x) now.y = -1;
if(now.x>now.y) {int tmp = now.x; now.x = now.y; now.y = tmp;}
gp2[x][i] = now;
}
sort(gp2[x].begin(), gp2[x].end());
vector<int> dp2(2000, 0);
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]==p[x][0]) continue;
for(int j=0; j<dp2.size(); j++){
if(((1<<i)&j)==0) continue;
dp2[j]+=dp[gp[x][i]];
}
}
for(int i=0; i<gp2[x].size(); i++){
E now = gp2[x][i];
if(now.x==-1){
for(int j=0; j<dp2.size(); j++){
if((j&(1<<now.y))!=0) continue;
dp2[j+(1<<now.y)] = max(dp2[j+(1<<now.y)], dp2[j]+now.z);
}
}else{
for(int j=0; j<dp2.size(); j++){
if((j&(1<<now.x))!=0) continue;
if((j&(1<<now.y))!=0) continue;
dp2[j+(1<<now.y)+(1<<now.x)] = max(dp2[j+(1<<now.y)+(1<<now.x)], dp2[j]+now.z);
}
}
}
for(int i=0; i<2000; i++) dp[x] = max(dp[x], dp2[i]);
dp2.clear();
return;
}
int degree[MAX_N+1];
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<M; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(c==0){
degree[a]++; degree[b]++;
gp[a].push_back(b); gp[b].push_back(a);
}else{
e.push_back({a, b, c});
ans+=c;
}
}
int now=1;
c[now] = 1;
lv[now] = 1;
dfs(now);
for(int i=0; i<e.size(); i++){
if(c[e[i].x]==c[e[i].y]){
gp2[lca(e[i].x, e[i].y)].push_back(e[i]);
}
}
dfs2(now);
ans-=dp[now];
printf("%d", ans);
return 0;
}
Compilation message
training.cpp: In function 'void dfs(int)':
training.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp2[x].size(); i++){
~^~~~~~~~~~~~~~
training.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[x].size(); j++){
~^~~~~~~~~~~~~
training.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
training.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<dp2.size(); j++){
~^~~~~~~~~~~
training.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp2[x].size(); i++){
~^~~~~~~~~~~~~~
training.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<dp2.size(); j++){
~^~~~~~~~~~~
training.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<dp2.size(); j++){
~^~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:148:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<e.size(); i++){
~^~~~~~~~~
training.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
training.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
420 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
632 KB |
Output is correct |
| 2 |
Correct |
12 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
1272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
