???

P3376 【模板】网络最大流

GTAISHAN @ 2022-12-12 15:27:14

求助,谢谢

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205;
const int M=10005;
const int INF=0x3f3f3f3f;
struct edge
{
    int v; 
    ll r;
    int next;
}es[M];
int n,m,s,t,cnt=1;
int flag[N][N];
int head[N];
queue<int> q;
bool vis[N];
int d[N];
int pre[N];
ll ans;
void addedge(int u,int v,int w)
{
    cnt++;
    es[cnt].v=v;
    es[cnt].r=w;
    es[cnt].next=head[u];
    head[u]=cnt;
}
bool bfs()
{
    memset(d,0x3f,sizeof(d));
    q=queue<int>();
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i>0;i=es[i].next)
        {
            int v=es[i].v;
            if(es[i].r>0 && d[v]==INF)
            {
                q.push(v);
                pre[v]=i;
                d[v]=d[u]+1;
                if (v==t) return true;
            }
        }
    }
}
int dfs(int x,ll flow)
{
    if(x==t) return flow;
    ll res=0,tmp;
    for(int i=head[x];i>0&&flow>0;i=es[i].next)
    {
        int v=es[i].v;
        if(es[i].r>0 && d[v]==d[x]+1)
        {
            tmp=dfs(v,min(flow,es[i].r));
            es[i].r-=tmp;
            es[i^1].r+=tmp;
            res+=tmp;
            flow-=tmp;
        }
    }
    return res;
}
int main()
{
    int u,v,w;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        if(!flag[u][v])
        {
            addedge(u,v,w);
            addedge(v,u,0);
            flag[u][v]=cnt;
        }
        else
        {
            es[flag[u][v]-1].r+=w;
        }
    }
    //Dinic算法 
    while(bfs())
    {
        ans+=dfs(s,INF);
    }
    cout<<ans<<endl;
    return 0;
}

by char_cha_ch @ 2022-12-12 15:31:36

@GTAISHAN bfs最后没返回值,不用判重,


by GTAISHAN @ 2022-12-12 15:39:12

@kirihara233 %%%您能在讲清楚点么,今天刚学没太明白


by char_cha_ch @ 2022-12-12 15:48:40

@GTAISHAN 感觉细节问题可能有点多。通常跑网络流都不用判重的,不为什么。你想,重边,依然还是可以流过去的对吧?除了这个知识点的问题可能没多少了。主要是注意一般 dis 数组初始值为 0 ,搞 inf 的话害怕值对不上。而且 next 里面 STL 有,一般都用 nxt。贴一份我的(话说你 Dinic 跑的比 EK 还慢耶

#include<cstdio>
#define N 209
#define M 10009

inline int read()
{
    register int ret = 0;
    register bool f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
        (ch == '-') ? f = 0 : 0, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getchar();
    return f ? ret : -ret;
}

struct node
{
    int v, w, nxt;
}e[M];

int head[N], cnt = 1;

inline void add(int u, int v, int w)
{
    e[++ cnt].v = v, e[cnt].w = w, e[cnt].nxt = head[u], head[u] = cnt;
}

int dis[N], now[N];

#include<queue>

using std::queue;

#include<cstring>

using std::memset;

int s, t;

inline bool bfs()
{
    memset(dis, -1, sizeof dis);
    queue < int > q;
    q.push(s);
    dis[s] = 0;
    now[s] = head[s];
    register int u, v, i;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        for (i = head[u];i;i = e[i].nxt)
        {
            v = e[i].v;
            if (e[i].w > 0 && dis[v] == -1)
            {
                dis[v] = dis[u] + 1;
                now[v] = head[v];
                if (v == t)
                    return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

#define min(a, b) (a < b ? a : b)

int dfs(register int u, register int flow = 1e9)
{
    if (u == t)
        return flow;
    register int lost = flow, i, v, w, k;
    for (i = now[u];i && lost;i = e[i].nxt)
    {
        v = e[i].v, w = e[i].w;
        if (w > 0 && dis[v] == dis[u] + 1)
        {
            k = dfs(v, min(lost, w));
            if (!k)
            {
                dis[v] = -1;
                continue;
            }
            lost -= k;
            e[i].w -= k;
            e[i & 1].w += k;
        }
    }
    return flow - lost;
}

int main()
{
    register int n = read(), m = read();
    s = read(), t = read();
    register int u, v, i;
    register long long ans = 0;
    for (i = 1;i <= m;++ i)
        u = read(), v = read(), add(u, v, read()), add(v, u, 0);
    while (bfs())
        ans += dfs(s);
    printf("%lld", ans);

    return 0;
}

每日信息学默写内容


by GTAISHAN @ 2022-12-12 15:51:42

@kirihara233 thx


|