Hdu 1532——Drainage Ditches

看了一会网络流的概念，找了个模板就上了。。起初TLE了几遍，发现是初始化没搞好。。

sap优化据资料说比EK省好多时间的说，网络流的精髓应该是构图，以后碰到难题应该会有所体会的。网络流有三个性质：一个节点流量守恒（形如电路中的KVL/KCL），流量双向，f(i,j)<=c(i,j)...

毕竟第一个网络流模板题的说，直接用SAP了。

[cpp]
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;

const int MAXN=400;    //边数
const int MAXM=40000; //顶点数
const int INF=0x7FFFFFF;

class Edge
{
public:
    int a,b;          //边从a->b
    int c,f;           //容量C,流量f
    Edge *next,*back;
    void setedge(int a,int b,int c,Edge *next)
    {
        this->a=a;
        this->b=b;
        this->c=c;
        this->next=next;
        this->back=NULL;
        this->f=0;

    }
};

Edge *edge[MAXN];
Edge nextedge[MAXM];

int dist[MAXN];
int edgenum=0;
int counts[MAXN];

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        edge[i]=NULL;
        counts[i]=0;
    }
    edgenum=0;
}

void init_lable(int n,int s,int t)//顶点个数n,源s,汇t
{
    queue<int> que;
    que.push(t);
    memset(dist,-1,sizeof(dist));
    dist[t]=0;
    ++counts[dist[t]];
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(Edge *next=edge[now]; next!=NULL;next=next->next)
        {
            if(next->f!=0)
                continue;
            int b=next->b;
            if(dist[b]==-1)
            {
                dist[b]=dist[now]+1;
                ++counts[dist[b]];
                que.push(b);
            }
        }
    }
}

void addedge(int x,int y,int c) //添加从x->y的弧，容量为c
{
    nextedge[edgenum].setedge(x,y,c,edge[x]);
    nextedge[edgenum+1].setedge(y,x,0,edge[y]);
    edge[x]=&nextedge[edgenum];
    edge[y]=&nextedge[edgenum+1];

    edge[x]->back=edge[y];
    edge[y]->back=edge[x];
    edgenum+=2;
}

int maxflow(int n,int s,int t)
{
    int ret=0;
    init_lable(n,s,t);
    Edge *path[MAXN];
    Edge *current[MAXN];

    memcpy(current,edge,sizeof(edge));

    int path_n=0;//路径长度
    int i=s;
    while(1)
    {
        if(i==t)//找到增广路
        {
            int minflow=INF;
            int mink;
            for(int k=0;k<path_n;k++)
            {
                if(path[k]->c<minflow)
                {
                    minflow=path[k]->c;
                    mink=k;
                }
            }
            ret+=minflow;
            for(int k=0;k<path_n;k++)
            {
                path[k]->c-=minflow;
                path[k]->back->c+=minflow;
                path[k]->f+=minflow;
                path[k]->back->f=-(path[k]->f);

            }
            path_n=mink;
            i=path[path_n]->a;
        }
        if(dist[i]!=0 && counts[dist[i]-1]==0)

补充：软件开发 , C++ ,