吉林大学ACM集训队选拔赛 J.Across the Firewall 网络流

题目链接：https://ac.nowcoder.com/acm/contest/5944/J
题目大意：有n台电脑，有m条通路。u-v-w双向u一秒能够发送w(kb)的数据到v。并且电脑也有转发速度的上限。每秒最多转发a[i]的数据。现在控制了第k台电脑，问从1号电脑发送s(kb)的数据到k电脑需要的最小时间。

思路：拆点最大流。ans=s/最大流

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef long long LL;
const LL maxn = 5005;
const LL INF = 0x3f3f3f3f;
LL cas = 1, T;
LL d[maxn], cur[maxn], start, tend;
struct node
{
    LL to, cap, next;
    //node(){}
    //node(LL a,LL b,LL c):to(a),cap(b),rev(c){}
} edge[maxn << 1];
//vector<node>mp[maxn];
LL head[maxn];
bool vis[maxn];
LL cnt;
void addedge(LL start, LL to, LL cap)
{
    edge[cnt].to = to;
    edge[cnt].cap = cap;
    edge[cnt].next = head[start];
    head[start] = cnt++;
}
bool BFS()
{
    //memset(vis,false,sizeof(vis));
    memset(d, -1, sizeof(d));
    LL Q[maxn * 2];
    LL Thead, Ttail;
    Thead = Ttail = 0;
    Q[Ttail++] = start;;
    d[start] = 0;
    //vis[start]=1;
    while (Thead<Ttail)
    {
        LL x = Q[Thead];
        if (x == tend)
            return true;
        for (LL i = head[x]; i != -1; i = edge[i].next)
        {
            LL temp = edge[i].to;
            if (d[temp] == -1 && edge[i].cap>0)//没有标记,且可行流大于0
            {
                //vis[temp.to]=true;
                d[temp] = d[x] + 1;
                Q[Ttail++] = temp;
            }
        }
        Thead++;
    }
    return false;//汇点是否成功标号,也就是说是否找到增广路
}
LL DFS(LL x, LL cap)
{
    if (x == tend)
        return cap;
    //vis[start]=true;
    LL flow = 0, f;
    for (LL i = head[x]; i != -1; i = edge[i].next)
    {
        LL temp = edge[i].to;
        //if(temp.cap<=0||vis[temp.to])continue;
        if (d[temp] == d[x] + 1 && edge[i].cap)
        {
            f = DFS(temp, min(cap - flow, edge[i].cap));
            edge[i].cap -= f;
            edge[i ^ 1].cap += f;
            flow += f;
            if (flow == cap)
                break;
        }
    }
    if (!flow)
        d[x] = -2;//防止重搜
    return flow;
}
LL maxflow()
{
    LL flow = 0, f;
    while (BFS())
    {
        //memset(vis,false,sizeof(vis));
        while ((f = DFS(start, INF))>0)
            flow += f;
    }
    return flow;
}

int main()
{
    LL n, m, T;
    cnt = 0; start=0;
    memset(head, -1, sizeof(head));
    scanf("%lld%lld", &n, &m);
    for(LL i=1; i<=n; i++){
        LL x; scanf("%lld", &x);
        addedge(i, i+n, x);
        addedge(i+n, i, 0);

        addedge(start, i, INF);
        addedge(i+n, start, 0);
    }

    for(int i=1; i<=m; i++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        addedge(x, y+n, 0);
        addedge(y+n, x, z);

        addedge(x+n, y, z);
        addedge(y, x+n, 0);
    }
    scanf("%lld%lld", &tend, &T);
    tend+=n;
    LL ans=maxflow();
    printf("%.8f\n", 1.0*T/ans);

    return 0;
}