新颖63分TLE法
查看原帖
新颖63分TLE法
507374
sqrtqwq楼主2024/5/14 16:31

4TLE,比较抽象,看了几个贴都没有发现错误

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;

namespace FOLW
{
    struct edge
    {
        int to,nxt,w,c;
    }e[maxn << 1];
    int head[maxn],tot;
    void add_edge(int u,int v,int w,int c)
    {
        e[++tot].nxt = head[u];
        head[u] = tot;
        e[tot].to = v;
        e[tot].w = w;
        e[tot].c = c;
    }
    void add(int u,int v,int w,int c)
    {
        add_edge(u,v,w,c);
        add_edge(v,u,0,-c);
    }
    int dis[maxn],now[maxn];
    bool vis[maxn];
    bool spfa(int s,int t)
    {
        memset(dis,63,sizeof(dis));
        memcpy(now,head,sizeof(head));
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        vis[s] = 1;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = head[u];i;i = e[i].nxt)
            {
                int v = e[i].to;
                if(e[i].w && dis[v] > dis[u] + e[i].c)
                {
                    dis[v] = dis[u] + e[i].c;
                    if(!vis[v])
                    {
                        q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    int ret;
    int dfs(int u,int t,int flow)
    {
        if(u == t)return flow;
        vis[u] = 1;
        int ans = 0;
        for(int i = now[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(!vis[v] && e[i].w && dis[v] == dis[u] + e[i].c)
            {
                int x = dfs(v,t,min(e[i].w,flow - ans));
                if(x)ret += x * e[i].c,e[i].w -= x,e[i ^ 1].w += x,ans += x;
            }
        }
        vis[u] = 0;
        return ans;
    }
    int dinic(int s,int t)
    {
        int ans = 0,flow = 0;
        while(spfa(s,t))
        {
            while(flow = dfs(s,t,INF))ans += flow;
        }
        return ans;
    }
}using namespace FOLW;
int n,m,s,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> s >> t;
    while(m--)
    {
        int u,v,w,c;
        cin >> u >> v >> w >> c;
        add(u,v,w,c);
    }
    int ans = dinic(s,t);
    cout << ans << " " << ret << '\n';
    return 0;
}

2024/5/14 16:31
加载中...