本机23ms但是全TLE?
查看原帖
本机23ms但是全TLE?
767099
WEXI7111楼主2023/6/21 22:01
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int h[N], nxt[N], w[N], c[N], to[N], idx = 1;
int d[N], mn[N], pre[N], S, T, m, n;
bool vis[N];

void add(int u, int v, int f, int co)
{
    to[++ idx] = v; w[idx] = f; c[idx] = co; nxt[idx] = h[u]; h[u] = idx;
    to[++ idx] = u; w[idx] = 0; c[idx] = -co; nxt[idx] = h[v]; h[v] = idx;
}

bool spfa()
{
    for(int i = 1; i <= n; i ++) d[i] = 1e9, mn[i] = 0;
    queue<int> q;
    q.push(S); d[S] = 0; mn[S] = 1e9;
    while(!q.empty())
    {
        int t = q.front(); q.pop(); vis[t] = 0;
        for(int i = h[t]; i != -1; i = nxt[i])
        {
            int e = to[i]; 
            if(w[i] && d[e] > d[t] + c[i])
            {
                d[e] = d[t] + c[i]; pre[e] = i;
                mn[e] = min(mn[t], w[i]);
                if(!vis[e]) {q.push(e); vis[e] = 1;}
            }
        }
    }
    return mn[T] > 0;
}

int EK(int &flow, int &cost)
{
    flow = cost = 0;
    while(spfa())
    {
        int t = mn[T]; flow += t, cost += t * d[T];
        for(int i = T; i != S; i = to[pre[i] ^ 1])
            w[pre[i]] -= t, w[pre[i] ^ 1] += t;
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d%d%d", &n, &m, &S, &T);
    while(m --)
    {
        int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
    }
    int flow, cost;
    EK(flow, cost);
    cout << flow << ' ' << cost;
    return 0;
}
2023/6/21 22:01
加载中...