438. The Glorious Karlutka River =)

题目大意：河中有一些漂浮物，每个漂浮物有一个容量。求m个人过河的最短时间。

题目思路：经典题目,加上时间限定条件,并且容量在点上,需要拆点,假设答案时间是T,那么每个点都要拆成2*T个点具体建法:S->SS为人数,SS->V无穷,UT,1->UT,2为点的容量,UT-1,2->VT,1无穷,UT-1,2->UT,1无穷,UT-1,2->T无穷效率关键是看怎么建图个方案和答案T的枚举,我用了四个方法,时间效率比较如下:sap(邻接表)按时间从小到大遍历,每次都重新建图重新增广2173MSsap(邻接表)二分时间,每次都重新建图重新增广409MSEK(邻接表)按时间从小到大,但是每次增加2*n个点后在原来的基础上增广47MSsap(邻接表)按时间从小到大,但是每次增加2*n个点后在原来的基础上增广(但是dis和gap初始化)772MS(这里sap比EK还慢,也许是因为每次推的时候dis和gap清空了(不初始化的话答案不出来),所以推的很慢,不知道有没有更好的算法)（以上思路摘自网上）
开始的时候我想到的就是拆点加二分，不敢确定，还是看了题解，看到题解有这总方法，试了一下，一直tle,于是还是只能用逐步加点的方式了，用dinic的模板过了。
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 55555
int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int x[100],y[100],c[100],m,n,d,w;
int dis[Max],p[Max];
int src,dest,eid,ans;
int q[Max];
struct node
{
     int to,c,next;
}e[2222222];
void addedge(int u,int v,int c)
{
    e[eid]=(node){v,c,p[u]};
    p[u]=eid++;
    e[eid]=(node){u,0,p[v]};
    p[v]=eid++;
}
int bfs()
{
    int i,u,v,head=0,tail=0;
    for(i=0;i<=dest+1;i++) dis[i]=0;
    dis[src]=1;
    q[tail++]=src;
    while(head<tail)
    {
        u=q[head++];
        for(i=p[u];~i;i=e[i].next)
            if(e[i].c&&dis[v=e[i].to]==0)
            {
                dis[v]=dis[u]+1;
                if(v==dest)
                    return 1;
                q[tail++]=v;
            }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==dest)
        return limit;
    int v,tmp,cost=0;
    for(int i=p[u];~i;i=e[i].next)
        if(e[i].c&&dis[u]+1==dis[v=e[i].to])
        {
            tmp=dfs(v,min(limit-cost,e[i].c));
            if(tmp)
            {
                e[i].c-=tmp;
                e[i^1].c+=tmp;
                cost+=tmp;
            }
            else
                dis[v]=-1;
        }
    return cost;
}
int Dinic()
{
    while(bfs())
        ans+=dfs(src,inf);
    return ans;
}
bool find(int u)
{
    int i;
    dis[u]=1;
    if(w-y[u]<=d)
    {
        dis[n+1]=1;
        return true;
    }
    for(i=1;i<=n;i++)
    {
        if(!dis[i]&&((x[u]-x[i])*(x[u]-x[i])+(y[u]-y[i])*(y[u]-y[i]))<=d*d)
        {
           if(find(i))
                return true;
        }
    }
    return false;
}
int main()
{
    int i,j,k;
    while(scanf("%d%d%d%d",&n,&m,&d,&w)!=EOF)
    {
        int cnt=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&c[i]);
            if(c[i]>0)
            {
                x[++cnt]=x[i];
                y[cnt]=y[i];
                c[cnt]=c[i];
            }
        }
        n=cnt;
        if(d>=w)
        {
            printf("1\n");
            continue;
        }
        for(i=0;i<=n+1;i++) dis[i]=0;

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