Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 4 KB
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 4 KB
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package hu.krivan.flow;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Collections;
import java.util.Vector;
/**
*
* @author Bálint Kriván
*/
public class Graph {
private int edgeCount;
private int[][] capacity;
private int nodeCount;
private int currentFlowSize;
private int[] daddy;
public Graph( int nodeCount, BufferedReader input ) throws IOException
{
this.nodeCount = nodeCount;
capacity = new int[nodeCount][nodeCount];
edgeCount = Integer.parseInt(input.readLine());
for( int i=0; i<nodeCount; i++ ) {
for( int j=0; j<nodeCount; j++ ) {
capacity[i][j] = 0;
// az alap kapacitás 0, mindenhol.
}
}
// kapacitások feltöltése.
String[] readLine;
for( int i=0; i<edgeCount; i++ ) {
readLine = input.readLine().split(" ");
capacity[Integer.parseInt(readLine[0])-1][Integer.parseInt(readLine[1])-1] =
Integer.parseInt(readLine[2]);
}
input.close();
}
private Graph() {
}
public int getCapacity( int u, int v )
{
if( u == -1 ) return -1;
return capacity[u][v];
}
/**
* Útkeresés a két pont között. Eközben magát az útvonalat is eltároljuk.
*
* @param from
* @param to
* @return igaz, ha létezik út
*/
public boolean hasRoute(int from, int to)
{
Vector<Integer> q = new Vector<Integer>(nodeCount);
q.add( from );
// inicializálás.
boolean[] checked = new boolean[nodeCount];
daddy = new int[nodeCount];
for( int i=0; i<nodeCount; i++ )
{
checked[i] = false;
daddy[i] = -1;
}
int node;
while( !q.isEmpty() ) {
node = q.remove(0);
if( checked[node] ) continue;
checked[node] = true;
for( int j=0; j<nodeCount; j++ )
{
// ha a két pont közötti kapacitás nem nulla és itt még nem jártunk
// akkor hozzáadjuk a sorhoz
if( getCapacity(node, j) > 0 && !checked[j] ) {
daddy[j] = node;
q.add( j );
}
}
}
// ha a célállomásnál jártunk a bejárás alatt, akkor létezik út.
return checked[to];
}
/**
* Egy adott folyamot indítunk a gráfban. A folyam méretét most számoljuk ki.
*
* @param source honnan indítjuk
* @param sink hova érkezzen
* @return folyam
*/
public int[][] getFlow( int source, int sink ) {
int[][] res = new int[nodeCount][nodeCount];
int minCapacity = -1;
// 1. út meghatározás. közben kiszámoljuk a legszűkebb keresztmetszetet.
Vector<Integer> route = new Vector<Integer>(daddy.length);
int node = sink;
int cap;
while( node != -1 ) {
route.add(node);
cap = getCapacity(daddy[node], node);
if( minCapacity == -1 || (cap != -1 && minCapacity > cap) ) {
minCapacity = cap;
}
node = daddy[node];
}
Collections.reverse(route);
// folyam felépítése
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
res[i][j] = 0;
int prev = route.get(0);
int cur;
for( int i=1; i<route.size(); i++ )
{
cur = route.get(i);
res[prev][cur] = minCapacity;
res[cur][prev] = -minCapacity;
prev = cur;
}
currentFlowSize += minCapacity;
return res;
}
public void makeChangesFromFlow(int[][] flow) {
// a beérkező folyamból kell generálni egy maradék-gráfot.
// az adott gráfon új folyamot indítunk, tehát minden kapacitást lecsökkentünk
// a folyam méretével, ahol az áthalad.
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
capacity[i][j] -= flow[i][j];
}
public int getFlowSize()
{
return currentFlowSize;
}
@Override
public Graph clone()
{
Graph clone = new Graph();
clone.nodeCount = nodeCount;
clone.edgeCount = edgeCount;
clone.currentFlowSize = currentFlowSize;
clone.capacity = new int[nodeCount][nodeCount];
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
clone.capacity[i][j] = capacity[i][j];
return clone;
}
}
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package hu.krivan.flow;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Collections;
import java.util.Vector;
/**
*
* @author Bálint Kriván
*/
public class Graph {
private int edgeCount;
private int[][] capacity;
private int nodeCount;
private int currentFlowSize;
private int[] daddy;
public Graph( int nodeCount, BufferedReader input ) throws IOException
{
this.nodeCount = nodeCount;
capacity = new int[nodeCount][nodeCount];
edgeCount = Integer.parseInt(input.readLine());
for( int i=0; i<nodeCount; i++ ) {
for( int j=0; j<nodeCount; j++ ) {
capacity[i][j] = 0;
// az alap kapacitás 0, mindenhol.
}
}
// kapacitások feltöltése.
String[] readLine;
for( int i=0; i<edgeCount; i++ ) {
readLine = input.readLine().split(" ");
capacity[Integer.parseInt(readLine[0])-1][Integer.parseInt(readLine[1])-1] =
Integer.parseInt(readLine[2]);
}
input.close();
}
private Graph() {
}
public int getCapacity( int u, int v )
{
if( u == -1 ) return -1;
return capacity[u][v];
}
/**
* Útkeresés a két pont között. Eközben magát az útvonalat is eltároljuk.
*
* @param from
* @param to
* @return igaz, ha létezik út
*/
public boolean hasRoute(int from, int to)
{
Vector<Integer> q = new Vector<Integer>(nodeCount);
q.add( from );
// inicializálás.
boolean[] checked = new boolean[nodeCount];
daddy = new int[nodeCount];
for( int i=0; i<nodeCount; i++ )
{
checked[i] = false;
daddy[i] = -1;
}
int node;
while( !q.isEmpty() ) {
node = q.remove(0);
if( checked[node] ) continue;
checked[node] = true;
for( int j=0; j<nodeCount; j++ )
{
// ha a két pont közötti kapacitás nem nulla és itt még nem jártunk
// akkor hozzáadjuk a sorhoz
if( getCapacity(node, j) > 0 && !checked[j] ) {
daddy[j] = node;
q.add( j );
}
}
}
// ha a célállomásnál jártunk a bejárás alatt, akkor létezik út.
return checked[to];
}
/**
* Egy adott folyamot indítunk a gráfban. A folyam méretét most számoljuk ki.
*
* @param source honnan indítjuk
* @param sink hova érkezzen
* @return folyam
*/
public int[][] getFlow( int source, int sink ) {
int[][] res = new int[nodeCount][nodeCount];
int minCapacity = -1;
// 1. út meghatározás. közben kiszámoljuk a legszűkebb keresztmetszetet.
Vector<Integer> route = new Vector<Integer>(daddy.length);
int node = sink;
int cap;
while( node != -1 ) {
route.add(node);
cap = getCapacity(daddy[node], node);
if( minCapacity == -1 || (cap != -1 && minCapacity > cap) ) {
minCapacity = cap;
}
node = daddy[node];
}
Collections.reverse(route);
// folyam felépítése
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
res[i][j] = 0;
int prev = route.get(0);
int cur;
for( int i=1; i<route.size(); i++ )
{
cur = route.get(i);
res[prev][cur] = minCapacity;
res[cur][prev] = -minCapacity;
prev = cur;
}
currentFlowSize += minCapacity;
return res;
}
public void makeChangesFromFlow(int[][] flow) {
// a beérkező folyamból kell generálni egy maradék-gráfot.
// az adott gráfon új folyamot indítunk, tehát minden kapacitást lecsökkentünk
// a folyam méretével, ahol az áthalad.
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
capacity[i][j] -= flow[i][j];
}
public int getFlowSize()
{
return currentFlowSize;
}
@Override
public Graph clone()
{
Graph clone = new Graph();
clone.nodeCount = nodeCount;
clone.edgeCount = edgeCount;
clone.currentFlowSize = currentFlowSize;
clone.capacity = new int[nodeCount][nodeCount];
for( int i=0; i<nodeCount; i++ )
for( int j=0; j<nodeCount; j++)
clone.capacity[i][j] = capacity[i][j];
return clone;
}
}
(Vissza)