Dinic TLE 85求调
查看原帖
Dinic TLE 85求调
1023189
wangtairan114楼主2025/1/27 13:12

rt,代码如下:

#include <cstring>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <limits.h>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
using namespace std;
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)<(b)?(b):(a))
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define f(nm1,nm2,nm3) for(ll nm1=nm2; nm1<= nm3; nm1++)
namespace flow{
int s,t;
vector<pair<int,ll>> v[30100];
map<pair<int,int>,pair<int,int>> mp;
void addedge(int x,int y,ll w){
    v[x].push_back({y,w});
    v[y].push_back({x,0});
    mp[{x,v[x].size()-1}]={y,v[y].size()-1};
    mp[{y,v[y].size()-1}]={x,v[x].size()-1};
}
int cur[30105],dep[30105];
bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s]=1;
    bool ok=0;
    while(q.size()){
        int x=q.front();
        if(x==t)
            ok=1;
        q.pop();
        for(auto y:v[x]){
            if(dep[y.v1]||!y.v2)
                continue;
            dep[y.v1]=dep[x]+1;
            q.push(y.v1);
        }
    }
    memset(cur,0,sizeof(cur));
    return ok;
}
ll dfs(int k,ll hsflow){
    if(k==t)
        return hsflow;
    for(int i=cur[k]; i < v[k].size(); i++){
        cur[k]=i;
        auto y=v[k][i];
        if(!y.v2||dep[k]+1!=dep[y.v1])
            continue;
        ll res=dfs(y.v1,min(hsflow,y.v2));
        if(!res){
            dep[y.v1]=0;
            continue;
        }
        v[k][i].v2-=res;
        v[mp[{k,i}].v1][mp[{k,i}].v2].v2+=res;
        return res;
    }
    return 0;
}
ll dinic(){
    ll ans=0;
    while(bfs())
        ans+=dfs(s,INF);
    return ans;
}
}
ll val[45][45][45];
int p,q,r,d;
map<pair<int,pair<int,int>>,int> mch;
int cnt=0;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int main(){
    sc("%d%d%d",&p,&q,&r);
    sc("%d",&d);
    flow::s=++cnt;
    flow::t=++cnt;
    for(int i=1; i <= r; i++){
        for(int j=1; j <= p; j++){
            for(int k=1; k <= q; k++){
                sc("%lld",&val[j][k][i]);
                mch[{j,{k,i}}]=++cnt;
            }
        }
    }
    for(int i=1; i <= p; i++){
        for(int j=1; j <= q; j++){
            flow::addedge(flow::s,mch[{i,{j,1}}],INF);
        }
    }
    for(int k=1; k < r; k++){
        for(int i=1; i <= p; i++){
            for(int j=1; j <= q; j++){
                flow::addedge(mch[{i,{j,k}}],mch[{i,{j,k+1}}],val[i][j][k]);
            }
        }
    }
    for(int i=1; i <= p; i++){
        for(int j=1; j <= q; j++){
            flow::addedge(mch[{i,{j,r}}],flow::t,val[i][j][r]);
        }
    }
    for(int i=1; i <= p; i++){
        for(int j=1; j <= q; j++){
            for(int k=1; k <=r; k++){
                if(k<=d)
                    continue;
                for(int l=0; l <4;l++){
                    int xx=i+dir[l][0];
                    int yy=j+dir[l][1];
                    if(xx>=1&&xx<=p&&yy>=1&&yy<=q){
                        flow::addedge(mch[{i,{j,k}}],mch[{xx,{yy,k-d}}],INF);
                    }
                }
            }
        }
    }
    cout << flow::dinic();
    return 0;
}
//p3227
2025/1/27 13:12
加载中...