import java.applet.Applet;
import java.applet.AppletContext;
import java.awt.*;
import java.io.*;
import java.net.URL;

public class Flux extends Applet
{

    int n;
    int m;
    int snode;
    int tnode;
    int pas;
    Node v[];
    Muchie e[];

    int findNode(String s)
    {
        for(int i = 0; i < n; i++)
        {
            if(v[i].nume.equals(s))
            {
                return i;
            }
        }

        return -1;
    }

    void input_graf(InputStream inputstream)
        throws IOException
    {
        StreamTokenizer streamtokenizer = new StreamTokenizer(inputstream);
        streamtokenizer.commentChar(35);
        streamtokenizer.nextToken();
        n = (int)streamtokenizer.nval;
        streamtokenizer.nextToken();
        m = (int)streamtokenizer.nval;
        streamtokenizer.nextToken();
        String s = streamtokenizer.sval;
        for(int i = 0; i < n; i++)
        {
            Node node = new Node();
            streamtokenizer.nextToken();
            node.nume = streamtokenizer.sval;
            streamtokenizer.nextToken();
            node.x = (int)streamtokenizer.nval;
            streamtokenizer.nextToken();
            node.y = (int)streamtokenizer.nval;
            v[i] = node;
        }

        for(int j = 0; j < m; j++)
        {
            Muchie muchie = new Muchie();
            streamtokenizer.nextToken();
            muchie.nume = streamtokenizer.sval;
            switch(streamtokenizer.nextToken())
            {
            case -2: 
                muchie.nod_plus = (int)streamtokenizer.nval;
                break;

            case -3: 
                muchie.nod_plus = findNode(streamtokenizer.sval);
                break;
            }
            switch(streamtokenizer.nextToken())
            {
            case -2: 
                muchie.nod_minus = (int)streamtokenizer.nval;
                break;

            case -3: 
                muchie.nod_minus = findNode(streamtokenizer.sval);
                break;
            }
            streamtokenizer.nextToken();
            muchie.capacitate = (int)streamtokenizer.nval;
            muchie.flux = 0;
            e[j] = muchie;
        }

        pas = 1;
    }

    void refacDrum()
    {
        for(int i = 0; i < n; i++)
        {
            v[i].delta_plus = v[i].delta_minus = -1;
        }

        for(int j = 0; j < m; j++)
        {
            e[j].delta_plus = e[j].delta_minus = -1;
        }

        for(int k = 0; k < m; k++)
        {
            int l = e[k].nod_plus;
            if(v[l].delta_plus == -1)
            {
                v[l].delta_plus = k;
            } else
            {
                for(l = v[l].delta_plus; e[l].delta_plus >= 0; l = e[l].delta_plus) { }
                e[l].delta_plus = k;
            }
            l = e[k].nod_minus;
            if(v[l].delta_minus == -1)
            {
                v[l].delta_minus = k;
            } else
            {
                for(l = v[l].delta_minus; e[l].delta_minus >= 0; l = e[l].delta_minus) { }
                e[l].delta_minus = k;
            }
        }

    }

    void stCale()
    {
        int ai[] = new int[100];
        for(int k = 0; k < n; k++)
        {
            v[k].prev = v[k].dist = -1;
            v[k].l = 0;
        }

        for(int l = 0; l < m; l++)
        {
            e[l].st = -1;
        }

        int j;
        int i = j = 0;
        boolean flag = false;
        ai[i] = snode;
        v[snode].dist = 0;
        int l1 = v[snode].delta_plus;
        int i1 = 0;
        for(; l1 >= 0; l1 = e[l1].delta_plus)
        {
            if(i1 < e[l1].capacitate)
            {
                i1 = e[l1].capacitate;
            }
        }

        v[snode].l = i1;
        for(; j <= i; j++)
        {
            int k2 = v[ai[j]].dist;
            for(int i2 = v[ai[j]].delta_plus; i2 >= 0; i2 = e[i2].delta_plus)
            {
                if(e[i2].capacitate - e[i2].flux != 0)
                {
                    int j1 = e[i2].nod_minus;
                    if(v[j1].dist < 0)
                    {
                        v[j1].dist = k2 + 1;
                        v[j1].prev = ai[j];
                        v[j1].p_muchie = i2;
                        v[j1].l = Math.min(v[ai[j]].l, e[i2].capacitate - e[i2].flux);
                        e[i2].st++;
                        ai[++i] = j1;
                    }
                }
            }

            for(int j2 = v[ai[j]].delta_minus; j2 >= 0; j2 = e[j2].delta_minus)
            {
                if(e[j2].flux != 0)
                {
                    int k1 = e[j2].nod_plus;
                    if(v[k1].dist < 0)
                    {
                        v[k1].dist = k2 + 1;
                        v[k1].prev = ai[j];
                        v[k1].p_muchie = j2;
                        v[k1].l = Math.min(v[ai[j]].l, e[j2].flux);
                        e[j2].st++;
                        ai[++i] = k1;
                    }
                }
            }

        }

    }

    void pas0()
    {
        for(int i = 0; i < m; i++)
        {
            e[i].flux = 0;
        }

        stCale();
    }

    void pas1()
    {
        if(v[tnode].dist < 0)
        {
            return;
        }
        for(int i = tnode; v[i].prev >= 0; i = v[i].prev)
        {
            e[v[i].p_muchie].st++;
        }

    }

    void pas2()
    {
        int l = v[tnode].l;
        int j;
        for(int i = tnode; (j = v[i].prev) >= 0; i = j)
        {
            int k = v[i].p_muchie;
            if(e[k].nod_minus == i)
            {
                e[k].flux += l;
            } else
            if(e[k].nod_plus == i)
            {
                e[k].flux -= l;
            }
        }

        stCale();
    }

    public void init()
    {
        String s = getParameter("inputfile");
        try
        {
            InputStream inputstream = (new URL(getDocumentBase(), s)).openStream();
            input_graf(inputstream);
            try
            {
                if(inputstream != null)
                {
                    inputstream.close();
                }
            }
            catch(Exception _ex) { }
        }
        catch(FileNotFoundException _ex)
        {
            System.err.println("File not found.");
        }
        catch(IOException _ex)
        {
            System.err.println("Cannot access file.");
        }
        String s1 = getParameter("s");
        if(s1 != null)
        {
            snode = Integer.parseInt(s1);
        } else
        {
            snode = 0;
        }
        s1 = getParameter("t");
        if(s1 != null)
        {
            tnode = Integer.parseInt(s1);
        } else
        {
            tnode = n - 1;
        }
        refacDrum();
        pas0();
    }

    public void paintNode(Graphics g, Node node, FontMetrics fontmetrics)
    {
        int i = node.x;
        int j = node.y;
        int k = fontmetrics.stringWidth(node.nume) + 10;
        int l = fontmetrics.getHeight() + 4;
        node.w = k;
        node.h = l;
        Color color;
        if(node.dist < 0)
        {
            color = Color.gray;
        } else
        {
            color = Color.blue;
        }
        g.setColor(color);
        g.drawRect(i - k / 2, j - l / 2, k, l);
        g.setColor(getBackground());
        g.fillRect((i - k / 2) + 1, (j - l / 2) + 1, k - 1, l - 1);
        g.setColor(color);
        g.drawString(node.nume, i - (k - 10) / 2, (j - (l - 4) / 2) + fontmetrics.getAscent());
    }

    int[] xy(int i, int j, int k, int l)
    {
        int ai[] = new int[2];
        if(Math.abs(k * j) >= Math.abs(l * i))
        {
            ai[0] = ((j < 0 ? -1 : 1) * i * l) / j / 2;
            ai[1] = ((j < 0 ? -1 : 1) * l) / 2;
        } else
        {
            ai[0] = ((i < 0 ? -1 : 1) * k) / 2;
            ai[1] = ((i < 0 ? -1 : 1) * j * k) / i / 2;
        }
        return ai;
    }

    void drawArrow(Graphics g, int i, int j, int k, int l)
    {
        int i1 = i - k;
        int j1 = j - l;
        double d = Math.sqrt(i1 * i1 + j1 * j1) / 16D;
        double d1 = (double)j1 / d;
        d = (double)i1 / d;
        g.drawLine(k, l, k + (int)((d * 12D + d1 * 5D) / 13D), l + (int)((-d * 5D + d1 * 12D) / 13D));
        g.drawLine(k, l, k + (int)((d * 12D - d1 * 5D) / 13D), l + (int)((d * 5D + d1 * 12D) / 13D));
        g.drawLine(i, j, k, l);
    }

    public void paintMuchie(Graphics g, Muchie muchie, FontMetrics fontmetrics)
    {
        Node node = v[muchie.nod_plus];
        Node node1 = v[muchie.nod_minus];
        int i = node.x - node1.x;
        int j = node.y - node1.y;
        int ai[] = xy(-i, -j, node.w, node.h);
        int ai1[] = xy(i, j, node1.w, node1.h);
        Color color;
        if(muchie.st > 0)
        {
            color = Color.red;
        } else
        if(node.dist >= 0 && node1.dist >= 0)
        {
            color = Color.blue;
        } else
        {
            color = Color.gray;
        }
        g.setColor(color);
        drawArrow(g, node.x + ai[0], node.y + ai[1], node1.x + ai1[0], node1.y + ai1[1]);
        int k = fontmetrics.stringWidth("" + muchie.flux + "/" + muchie.capacitate);
        int l = fontmetrics.getHeight();
        g.setColor(getBackground());
        g.fillRect(((node.x + node1.x) - k) / 2, ((node.y + node1.y) - l) / 2, k, l);
        g.setColor(Color.black);
        g.drawString("" + muchie.flux + "/" + muchie.capacitate, ((node.x + node1.x) - k) / 2, ((node.y + node1.y) - l) / 2 + fontmetrics.getAscent());
    }

    public void paint(Graphics g)
    {
        FontMetrics fontmetrics = g.getFontMetrics();
        for(int i = 0; i < n; i++)
        {
            paintNode(g, v[i], fontmetrics);
        }

        for(int j = 0; j < m; j++)
        {
            paintMuchie(g, e[j], fontmetrics);
        }

/**/
	int fluxM=0;
	for(int q=0;q<m;q++){
		if (e[q].nod_plus==snode) fluxM+=e[q].flux;
		}
	showStatus("Fluxul Maxim calculat este: "+fluxM);
/**/
        GrafRezidual reziduu = (GrafRezidual)getAppletContext().getApplet("reziduu");
        if(reziduu != null)
        {
            reziduu.set(1, n, m, snode, tnode, v, e);
        }
    }

    public void update(Graphics g)
    {
        paint(g);
    }

	
	
    public boolean mouseDown(Event event, int i, int j)
    {
        if(pas == 1)
        {
            pas1();
            if(v[tnode].dist < 0)
            {
                pas = 0;
            } else
            {
                pas = 2;
            }
        } else
        if(pas == 2)
        {
            pas2();
            pas = 1;
        } else
        {
            pas0();
            pas = 1;
        }
        
        repaint();
 
        return true;
    }

    public Flux()
    {
        v = new Node[100];
        e = new Muchie[200];
    }
}