結果
問題 | No.317 辺の追加 |
ユーザー |
|
提出日時 | 2016-03-25 01:04:16 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,723 ms / 2,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 2,502 ms |
コンパイル使用メモリ | 77,952 KB |
実行使用メモリ | 70,780 KB |
最終ジャッジ日時 | 2024-10-02 00:20:26 |
合計ジャッジ時間 | 55,233 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
package yukicoder317;import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();DJSet ds=new DJSet(n);for(int i=0;i<m;i++){ds.union(sc.nextInt()-1,sc.nextInt()-1);}int[] dp=new int[n+1];int[] f=new int[n+1];for(int i=0;i<n;i++){if(ds.upper[i]<0){f[-ds.upper[i]]++;}}Arrays.fill(dp, 999999999);dp[0]=0;int sum=0;for(int i=1;i<=n;i++){for(int d=1;f[i]>0;d*=2){int x=Math.min(f[i],d);f[i]-=x;//辺数iのグラフがf[i]個ある。sum+=x*i;for(int j=sum;j>=x*i;j--){dp[j]=Math.min(dp[j], dp[j-x*i]+x);}}}for(int i=0;i<=n;i++){if(dp[i]>1000000)dp[i]=0;}for(int i=1;i<=n;i++){System.out.println(dp[i]-1);}}public static class DJSet{public int[] upper;public DJSet(int n){upper=new int[n];Arrays.fill(upper, -1);}public int root(int x){return upper[x]<0? x:root(upper[x]);}public boolean equiv(int x,int y){return root(x)==root(y);}public boolean union(int x,int y){x=root(x);y=root(y);if(x!=y){if(upper[y]<upper[x]){int d=y;y=x;x=d;}upper[x]+=upper[y];upper[y]=x;}return x!=y;}public int size(int x){return -upper[root(x)];}public int count(){int ct=0;for(int u:upper)if(u<0)ct++;return ct;}}}