Submission #1416777

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
typedef vector<int> vi;
typedef pair<int,int> pii;

int n,m,k;
vector<pii> g[125];
int eid[125][125];
int cst[125][125];
int c2[12525];
pii edges[12525];
bool cycled[12525];

int data[125];
int root(int x){
  return data[x]<0?x:data[x]=root(data[x]);
}
void unite(int a,int b){
  a = root(a);
  b = root(b);
  if(a!=b){
    if(data[a]>data[b])swap(a,b);
    data[a] += data[b];
    data[b] = a;
  }
}

bool used[125];
deque<int> stk;
bool dfs(int p,int bef){
  stk.push_back(p);
  if(used[p]){
    return true;
  }
  used[p] = true;
  for(pii to : g[p])if(to.first!=bef){
    if(dfs(to.first,p)){
      return true;
    }
  }
  used[p] = false;
  stk.pop_back();
  return false;
}

int main(){
  scanf("%d%d%d",&n,&m,&k);
  REP(i,n)data[i] = -1;
  REP(i,n)REP(j,n)eid[i][j] = -1;
  REP(i,m){
    int f,t,c;
    scanf("%d%d%d",&f,&t,&c);
    --f;--t;
    unite(f,t);
    g[f].push_back(pii(t,c));
    g[t].push_back(pii(f,c));
    eid[f][t] = eid[t][f] = i;
    cst[f][t] = cst[t][f] = c;
    c2[i] = c;
    edges[i] = pii(c,i);
  }
  sort(edges,edges+m);
  REP(i,n)if(i==root(i))k--;
  // cycle
  REP(i,n)if(i==root(i)){
    if(dfs(i,-1)){
      // cycle
      int cyclebegin = stk.back();
      while(stk.front() != cyclebegin){
        stk.pop_front();
      }
      stk.pop_front();
      break;
    }
  }
  int ans = 1252183025;
  if(stk.size() > 0){
    // cycle
    int cid = -1;
    REP(i,stk.size()){
      int s = stk[i];
      int t = stk[(i+1)%stk.size()];
      int id = eid[s][t];
      if(cid==-1 || c2[cid] > c2[id]){
        cid = id;
      }
      cycled[id] = true;
    }
    int tmp = c2[cid];
    int x = k;
    REP(i,m){
      if(x<=0)break;
      if(edges[i].second == cid)continue;
      x--;
      tmp += edges[i].first;
    }
    ans = min(ans,tmp);
  }
  {
    int tmp = 0;
    int x = k;
    REP(i,m){
      if(x<=0)break;
      int id = edges[i].second;
      if(cycled[id])continue;
      x--;
      tmp += edges[i].first;
    }
    if(x<=0)ans = min(ans,tmp);
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&n,&m,&k);
                           ^
./Main.cpp:54:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&f,&t,&c);
                             ^

Judge Result