样例TLE求助
  • 板块P3254 圆桌问题
  • 楼主CJ_Fu
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/17 20:35
  • 上次更新2024/7/17 20:43:21
查看原帖
样例TLE求助
539344
CJ_Fu楼主2024/7/17 20:35
#include<bits/stdc++.h>
#define int long long
const int maxn=10003;
const int inf=0x3f3f3f3f;
using namespace std;
struct edge{
    int v,c,id;
    edge(int v=0,int c=0,int id=0): v(v),c(c),id(id){}
};
vector<edge>e[maxn];
int h[maxn],dep[maxn],siz[maxn];
int n,k,cnt,S,T; 
void add(int u,int v,int w){
    e[u].emplace_back(edge(v,w,siz[v])); 
    e[v].emplace_back(edge(u,0,siz[u])); 
    siz[u]++; siz[v]++;
}
queue<int>q;
int bfs(){
    for(int i=0;i<=cnt;i++) dep[i]=0;
    dep[T]=0; q.push(S); dep[S]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<siz[u];i++){
            edge v=e[u][i];
            if(v.c&&!dep[v.v]){
                dep[v.v]=dep[u]+1;
                q.push(v.v);
            }
        } 
    }
    return dep[T];
}
int dfs(int u,int flow){
    int ans=0;
    if(u==T) return flow;
    for(int& i=h[u];i<siz[u];i++){
        edge v=e[u][i];
        if(v.c&&dep[v.v]==dep[u]+1){
            int ret=dfs(v.v,min(flow-ans,v.c));
            ans+=ret,e[u][i].c-=ret,e[v.v][v.id].c+=ret;
        }
        if(ans==flow) return ans;
    }
    return ans;
}
int dinic(){
    int ans=0;
    while(bfs()){
        for(int i=1;i<=cnt;i++) h[i]=0;
        h[T]=0;
        ans+=dfs(S,inf);
    }
    return ans;
}
int con[maxn],m,a[maxn],c[maxn];
signed main(){
    cin>>k>>n;
    S=0;
    cnt=n;
    for(int i=1;i<=k;i++){
        con[i]=++cnt;
        cin>>a[i]; m+=a[i];
        add(S,con[i],a[i]);
    }
    T=++cnt;
    for(int i=1;i<=n;i++){
        cin>>c[i]; 
        for(int j=1;j<=k;j++){
            add(con[j],i,1);
        }
        add(i,T,c[i]);
    }
    // for(int i=0;i<=n+k+1;i++){
    //     cerr<<i<<'|';
    //     for(edge v:e[i]){
    //         if(v.c) cerr<<v.v<<' ';
    //     }
    //     cerr<<'\n';
    // }
    if(dinic()>=m){
        cout<<1<<'\n';
        for(int i=1;i<=k;i++){
            for(int j=1,u=1;j<=a[i];u++){
                edge v=e[con[i]][u];
                if(e[v.v][v.id].c) cout<<v.v<<' ',j++;
            }
            cout<<'\n';
        }
    }else{
        cout<<0;
    }
    return 0;
}
2024/7/17 20:35
加载中...