从前天开始，老子就一直调一直调POJ1273，不容易啊

前几天打算的使用dinic解决这个问题的，但是总是有各种问题，各种小bug

今天在网上可能到了某个仁兄发的日志，到了源代码，终于老子也把这个题目A掉了

在A题的过程中，我除了用我看到了网上那个写的代码（用数组存边）的并且写了一次，我还自己写了一个用邻接链表存边的程序。

但这些都不是最关键的。

关键的是我终于懂了求最大流的思想，并且把程序调试了出来。

今天写的是相对其他几个求最大流来说，思想最为容易的一个算法——EK算法

当然我觉得这个算法的时间复杂度还是比较可观的，只要那个出题者不故意弄那种奇葩的数据应该都不会TML，若加上邻接链表空间上也是毫无压力的。

算法的主要思想是对于图的图求从源点到终点的最大流量。

第一步就BFS，找到终点那T并且记录上一级点，从而等于是把整条路径都记录了下来，这样的话方便DFS修改路径。

第二步就是找flow（目前找到的增广路所能承受的最大流量，也就是该增广路中剩余容量最小的边）

第三步，给路径上每天表都减去flow，这样相当于该路径增加了flow的流量，故剩余容量应减去flow，同时把flow加到总共最大流ans上。

不断重复这三步，直到找不到增广路为止。

最后的答案ans就是所求的最大流。

贴两个个代码吧（一个用数组存边，一个用邻接链表）

第一个用数组存边，空间开销比较大，时间上两种基本一样，更大的优点是代码短小精悍。

＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <queue>
#define maxn 220
#define INF ~0U>>1
using namespace std;

int n,m,a[maxn][maxn],pre[maxn];

bool BFS(int s,int t)
{
    int now;
    queue<int> Q;
    memset(pre,0xff,sizeof(pre));
    pre[s]=0;
    Q.push(s);
    while (!Q.empty())
    {
        now=Q.front();
        Q.pop();
        for (int i=1; i<=n; i++)
            if (a[now][i]>0 && pre[i]==-1)
                pre[i]=now,Q.push(i);
        if (pre[t]>0) return true;
    }
    return false;
}

int maxflow(int s,int t)
{
    int flow,ans=0;
    while (BFS(s,t))
    {
        flow=INF;
        for (int i=t; pre[i]>0; i=pre[i])
            flow=min(flow,a[pre[i]][i]);
        for (int i=t; pre[i]>0; i=pre[i])
            a[pre[i]][i]-=flow,a[i][pre[i]]+=flow;
        ans+=flow;
    }
    return ans;
}


int main()
{
    int si,ei,ci;
    while (scanf("%d%d",&m,&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        while (m--)
        {
            scanf("%d%d%d",&si,&ei,&ci);
            a[si][ei]+=ci;
        }
        printf("%d\n",maxflow(1,n));
    }
    return 0;
}

第二种用邻接链表存表，空间上毫无压力，时间上和第一个一样，只是……代码量大了一些，调试也相对困难一点。 

＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <queue>
#define SUP ~0U>>2
#define maxn 220
#define bug cout<<"Here I got a bug  $%$#%$"<<endl
using namespace std;

struct edge{
    int si,ei,ci,next;
}s[100*maxn];

int first[maxn],n,m,pre[maxn],E;

void add_edge(int Si,int Ei,int Ci)
{
    s[E].si=Si;
    s[E].ei=Ei;
    s[E].ci=Ci;
    s[E].next=first[Si];
    first[Si]=E;
    E++;
}

bool BFS(int S,int T)
{
    int now;
    queue<int> Q;
    memset(pre,0xff,sizeof(pre));
    pre[S]=-2;
    Q.push(S);
    while (!Q.empty())
    {
        now=Q.front();
        Q.pop();
        for (int i=first[now]; i>=0; i=s[i].next)//枚举now为起点的边
        {
            if (s[i].ci>0 && pre[s[i].ei]==-1)
            {
                pre[s[i].ei]=i;
                Q.push(s[i].ei);
                if (pre[T]>=0) return true;
            }
        }
    }
    return false;
}

int maxflow(int S,int T)
{
    int flow,ans=0;
    while (BFS(S,T))
    {
        flow=SUP;
        for (int i=T; pre[i]>=0; i=s[pre[i]].si)
            flow=min(flow,s[pre[i]].ci);
        for (int i=T; pre[i]>=0; i=s[pre[i]].si)
            s[pre[i]].ci-=flow,s[pre[i]^1].ci+=flow;
        ans+=flow;
    }
    return ans;
}

int main()
{
    int Si,Ei,Ci;
    while (scanf("%d%d",&m,&n)!=EOF)
    {
        E=0;
        memset(first,0xff,sizeof(first));
        while (m--)
        {
            scanf("%d%d%d",&Si,&Ei,&Ci);
            add_edge(Si,Ei,Ci);
            add_edge(Ei,Si,0);
        }
        printf("%d\n",maxflow(1,n));
    }
}


接下来我还要学SAP，学完照样会把自己所学的发在博客里面，不过dinic就不发了，算法比较冗，而且时间也不优。

嘻嘻~~~~~~~~~~~~~~~~~