AOJ1065 The House of Huge Family

問題リンク The House of Huge Family

• 解法

まず、入力の制約の「Yiは重複しない」に注目すると辺の数は高々N個だと分かります。さらに、負の重みを持つ辺は取り除いた方が絶対得なので無条件で取り除くことにします。
問題の条件を満たす家の構造を考えたとき、辺の向きは意味を持たないので無向辺と見なします。このとき、グラフが2つ以上の連結成分に分かれているならば、条件を満たしています。
N個の頂点からなるグラフが全て連結しているための必要な辺の最小本数はN-1個です。つまり、辺の本数がN-2本以下ならば必ずグラフは森のような形をしていることになるので、取り除く辺は高々2本まででいいと分かります。あとは、取り除く辺が0本の場合、1本の場合、2本の場合を全て調べてみることで答えが求まります。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//The House of Huge Family
public class AOJ1065 {

	class E{
		int s, t, c, id;
		public E(int s, int t, int c, int id) {
			this.s = s;
			this.t = t;
			this.c = c;
			this.id = id;
		}
	}
	
	int n, m;
	List<E>[] adj;
	
	boolean isCon(int f1, int f2){
		boolean[] u = new boolean[n];
		List<Integer> l = new ArrayList<Integer>();
		l.add(0); u[0] = true;
		int N = 0;
		while(!l.isEmpty()){
			List<Integer> next = new ArrayList<Integer>();
			for(int i:l){
				N++;
				for(E e:adj[i])if(!u[e.t]&&e.id!=f1&&e.id!=f2){
					u[e.t] = true; next.add(e.t);
				}
			}
			l = next;
		}
		return N==n;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			adj = new List[n];
			for(int i=0;i<n;i++)adj[i]=new ArrayList<E>();
			int N = 0, M = 0;
			List<Integer> cost = new ArrayList<Integer>();
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), c = sc.nextInt();
				if(c<=0)M+=c;
				else{
					cost.add(c); adj[s].add(new E(s, t, c, N)); adj[t].add(new E(t, s, c, N)); N++;
				}
			}
			int min = Integer.MAX_VALUE;
			if(!isCon(-1, -1))min = 0;
			for(int i=0;i<N;i++)if(!isCon(i, -1))min = Math.min(min, cost.get(i));
			for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)min = Math.min(min, cost.get(i)+cost.get(j));
			System.out.println(M+min);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1065().run();
	}
}