QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589898#602. 最小费用最大流(随机数据)TauLee01Compile Error//C++171.9kb2024-09-25 20:32:372024-09-25 20:32:38

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 20:32:38]
  • 评测
  • [2024-09-25 20:32:37]
  • 提交

answer

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

const int Maxn = 510, Maxm = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct node {
    int to, nex, w, c;
} eg[Maxm];
bool vis[Maxn];
int tot = 1, fee, cur[Maxn], dis[Maxn], head[Maxn];

void add(int u, int v, int w, int c) {
    eg[++tot].to = v;
    eg[tot].w = w;
    eg[tot].c = c;
    eg[tot].nex = head[u];
    head[u] = tot;
}

void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }

bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis)); //初始距离为无穷
    memcpy(cur, head, sizeof(head)); //当前出初始化为head的第一个
    std::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 = eg[i].nex) {
            int v = eg[i].to;
            if (eg[i].w && dis[v] > dis[u] + eg[i].c) {
                dis[v] = dis[u] + eg[i].c;
                if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
    return dis[t] != INF;
}

int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    vis[u] = 1;
    int ans = 0;
    for (int &i = cur[u]; i && ans < flow; i = eg[i].nex) {
        int v = eg[i].to;
        if (!vis[v] && eg[i].w && dis[v] == dis[u] + eg[i].c) {
            int x = dfs(v, t, std::min(eg[i].w, flow - ans));
            if (x) fee += x * eg[i].c, eg[i].w -= x, eg[i ^ 1].w += x, ans += x;
        }
    }
    vis[u] = 0;
    return ans;
}

int dinic(int s, int t) {
    int ans = 0;
    while (spfa(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
signed main()
{
    int n;
    cin >> n;
int m;
cin>>m;
int u,v,w,c;
for(int i=1;i<=m;i++){
cin>>u>>v>>w>>c;
addedge(u,v,w,c);
}
    // 最小费用
    //addedge(i, j, w, c);

    int ans = dinic(s, t);
    debug(ans, fee);

cout<<ans<<" "<<fee<<endl;

}

Details

answer.code:1:9: fatal error: bits.stdc++.h: No such file or directory
    1 | #include<bits.stdc++.h>
      |         ^~~~~~~~~~~~~~~
compilation terminated.