<![CDATA[import java.io.*;
import java.util.*;
class Vertex {
int idNum, capacity, edgeFlow;
boolean forward; // direction;
Vertex twin; // edge in opposite direction;
Vertex() {
}
Vertex(int id, int c, int ef, boolean f) {
idNum = id; capacity = c; edgeFlow = ef; forward = f; twin = null;
}
public boolean equals(Object v) {
return idNum == ((Vertex)v).idNum;
}
public String toString() {
return (idNum + " " + capacity + " " + edgeFlow + " " + forward);
}
}
class VertexInVector {
String idName;
int vertexSlack;
boolean labeled = false;
int parent;
LinkedList adjacent = new LinkedList();
Vertex corrVer; // corresponding vertex: vertex on parent's
VertexInVector() { // list of adjacent vertices with the same
} // idNum as the cell's index;
VertexInVector(String s) {
idName = s;
}
public boolean equals(Object v) {
return idName.equals(((VertexInVector)v).idName);
}
public void display() {
System.out.print(idName + ' ' + vertexSlack + ' '
+ labeled + ' ' + parent + ' ' + corrVer + "-> ");
System.out.print(adjacent);
System.out.println();
}
}
class Network {
public Network() {
vertices.insertElementAt(new VertexInVector(), source);
vertices.insertElementAt(new VertexInVector(), sink);
((VertexInVector)vertices.elementAt(source)).idName = "source";
((VertexInVector)vertices.elementAt(sink)).idName = "sink";
((VertexInVector)vertices.elementAt(source)).parent = none;
}
protected final int sink = 1, source = 0, none = -1;
protected Vector vertices = new Vector();
protected int edgeSlack(Vertex u) {
return u.capacity - u.edgeFlow;
}
protected boolean labeled(Vertex p) {
return ((VertexInVector)vertices.elementAt(p.idNum)).labeled;
}
public void display() {
for (int i = 0; i < vertices.size(); i++) {
System.out.print(i + ": " );
((VertexInVector)vertices.elementAt(i)).display();
}
}
public void readCommittees(String fileName, InputStream fIn) {
int ch = 1, pos, commPos;
String s;
boolean lastMember;
Vertex memberVer, commVer;
VertexInVector committee, member;
try {
while (ch > -1) {
while (true)
if (ch > -1 && !Character.isLetter((char)ch)) // skip
ch = fIn.read(); // non-letters;
else break;
if (ch == -1)
break;
s = "";
while (ch > -1 && ch != ':') {
s += (char)ch;
ch = fIn.read();
}
committee = new VertexInVector(s.trim());
commPos = vertices.size();
commVer = new Vertex(commPos,1,0,false);
vertices.addElement(committee);
for (lastMember = false; !lastMember; ) {
while (true)
if (ch > -1 && !Character.isLetter((char)ch)) // skip
ch = fIn.read(); // non-letters;
else break;
if (ch == -1)
break;
s = "";
while (ch > -1 && ch != ',' && ch != ';') {
s += (char)ch;
ch = fIn.read();
}
if (ch == ';')
lastMember = true;
member = new VertexInVector(s.trim());
memberVer = new Vertex(0,1,0,true);
if ((pos = vertices.indexOf(member)) == -1) {
memberVer.idNum = vertices.size();
member.adjacent.addFirst(new Vertex(sink,1,0,true));
member.adjacent.addFirst(commVer);
vertices.addElement(member);
}
else {
memberVer.idNum = pos;
((VertexInVector)vertices.elementAt(pos)).
adjacent.addFirst(commVer);
}
committee.adjacent.addFirst(memberVer);
memberVer.twin = commVer;
commVer.twin = memberVer;
}
commVer = new Vertex(commPos,1,0,true);
((VertexInVector)vertices.elementAt(source)).adjacent.
addFirst(commVer);
}
} catch (IOException io) {
}
display();
}
private void label(Vertex u, int v) {
VertexInVector uu = (VertexInVector) vertices.elementAt(u.idNum);
VertexInVector vv = (VertexInVector) vertices.elementAt(v);
uu.labeled = true;
if (u.forward)
uu.vertexSlack = Math.min(vv.vertexSlack,edgeSlack(u));
else uu.vertexSlack = Math.min(vv.vertexSlack,u.edgeFlow);
uu.parent = v;
uu.corrVer = u;
}
private void augmentPath() {
int sinkSlack = ((VertexInVector)vertices.elementAt(sink)).vertexSlack;
Vertex u;
VertexInVector vv;
Stack path = new Stack();
for (int i = sink; i != source;
i = ((VertexInVector)vertices.elementAt(i)).parent) {
vv = (VertexInVector) vertices.elementAt(i);
path.push(vv.idName);
if (vv.corrVer.forward)
vv.corrVer.edgeFlow += sinkSlack;
else vv.corrVer.edgeFlow -= sinkSlack;
if (vv.parent != source && i != sink)
vv.corrVer.twin.edgeFlow = vv.corrVer.edgeFlow;
}
for (int i = 0; i < vertices.size(); i++)
((VertexInVector)vertices.elementAt(i)).labeled = false;
System.out.print(" source");
while (!path.isEmpty())
System.out.print(" => " + path.pop());
System.out.print(" (augmented by " + sinkSlack + ");\n");
}
public void FordFulkersonMaxFlow() {
int i, v;
Vertex u;
Iterator it;
Stack labeledS = new Stack();
for (i = 0; i < vertices.size(); i++)
((VertexInVector) vertices.elementAt(i)).labeled = false;
((VertexInVector)vertices.elementAt(source)).vertexSlack =
Integer.MAX_VALUE;
labeledS.push(new Integer(source));
System.out.println("Augmenting paths:");
while (!labeledS.isEmpty()) { // while not stuck;
v = ((Integer) labeledS.pop()).intValue();
for (it = ((VertexInVector)vertices.elementAt(v)).adjacent.iterator();
it.hasNext(); ) {
u = (Vertex) it.next();
if (!labeled(u)) {
if (u.forward && edgeSlack(u) > 0 ||
!u.forward && u.edgeFlow > 0)
label(u,v);
if (labeled(u))
if (u.idNum == sink) {
augmentPath();
labeledS.clear(); // look for another path;
labeledS.push(new Integer(source));
break;
}
else {
labeledS.push(new Integer(u.idNum));
((VertexInVector)vertices.elementAt(u.idNum)).
labeled = true;
}
}
}
}
}
}
class DistinctRepresentatives {
static public void main(String args[]) {
String fileName = "";
Network net = new Network();
InputStream fIn;
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader buffer = new BufferedReader(isr);
try {
if (args.length == 0) {
System.out.print("Enter a file name: ");
fileName = buffer.readLine();
fIn = new FileInputStream(fileName);
}
else {
fIn = new FileInputStream(args[0]);
fileName = args[0];
}
net.readCommittees(fileName,fIn);
fIn.close();
} catch(IOException io) {
System.err.println("Cannot open " + fileName);
}
net.FordFulkersonMaxFlow();
net.display();
}
}
]]>