Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-21

PKU 3538 -- Domestic Networks

| 17:45 | PKU 3538 -- Domestic Networks - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3538 -- Domestic Networks - Wrong Answer -- japlj PKU 3538 -- Domestic Networks - Wrong Answer -- japlj のブックマークコメント

最小全域木を求めてから、安い方のケーブルをできるだけ使う。安い方をどれだけ使えるかはDPで求める。


#include<cstdio>
#include<algorithm>

using namespace std;

int U[1024];
void init(int n) { for(int i=1; i<=n; ++i) U[i]=i; }
int find(int x) { return x!=U[x] ? U[x]=find(U[x]) : U[x]; }
void uni(int x, int y) { U[find(x)]=find(y); }

struct edge { int a, b, c, i; } E[10000];
bool operator < (const edge& e, const edge& f) {
  return e.c < f.c;
}

int main()
{
  int n, m, e=0, s=0, use[1000], p[2], q[2], r[2]={5,6};
  scanf("%d%d", &n, &m);
  for(int i=0; i<m; ++i)
    scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c), E[i].i=i;
  sort(E, E+m); init(n);
  for(int i=0; i<m; ++i) {
    if(find(E[i].a) == find(E[i].b)) continue;
    use[e++] = i; s += E[i].c;
    uni(E[i].a, E[i].b);
  }
  if(e!=n-1) { puts("Impossible"); return 0; }
  scanf("%d%d%d%d", &p[0], &q[0], &p[1], &q[1]);
  if(p[0]>p[1]) swap(p[0],p[1]), swap(q[0],q[1]), swap(r[0],r[1]);
  int dp[10001]={0}, ch[10001], cat[10000], use0;
  dp[0] = 1;
  for(int i=0, cost; i<e&&(cost=E[use[i]].c); cat[use[i++]]=1)
    for(int j=q[0]-cost; j>=0; --j)
      if(dp[j] && !dp[j+cost])
	dp[j+cost]=1, ch[j+cost]=i;
  for(use0=q[0]; !dp[use0]; use0--) ;
  if(s - use0 > q[1]) { puts("Impossible"); return 0; }
  for(int u=use0; u; u-=E[use[ch[u]]].c) cat[use[ch[u]]] = 0;
  printf("%d\n", p[0]*use0 + p[1]*(s-use0));
  for(int i=0; i<e; ++i)
    printf("%d %d\n", E[use[i]].i+1, r[cat[use[i]]]);
  return 0;
}
 |