CF AC,UVa WA是怎么回事呢
查看原帖
CF AC,UVa WA是怎么回事呢
251723
Schwarzkopf_Henkal楼主2021/2/8 14:18

Rt,一样的题,CF AC了,UVa WA。

CF的题要加文操,我在UVa上加不加文操都WA,是没有SPJ还是怎样?

CF提交见https://codeforces.com/gym/101308/status

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v;
    long long c,w,d;
};
struct LimitMax{
    const static int N=100005;
    int n,m,s,t;
    vector<Edge>E;
    vector<int>to[N];
    int d[N],C[N];//去掉了当前弧优化 | 又加上了(
    bool vis[N];
    long long val[N];
    void clear(int n){
        for(int i=1;i<=n;i++)
            to[i].clear();
        to[N-1].clear();
        to[N-2].clear();
        memset(val,0,sizeof(val));
        E.clear();
    }
    void NativeAE(int u,int v,long long w){
        E.push_back({u,v,w,0});
        E.push_back({v,u,0,0});
        m=E.size();
        to[u].push_back(m-2);
        to[v].push_back(m-1);
    }
    void AddEdge(int u,int v,long long c,long long d){
        n=max(n,max(u,v));
        val[u]-=c;
        val[v]+=c;
        NativeAE(u,v,d-c);
        E[m-2].d=c;
    }
    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int>que;
        que.push(s);
        d[s]=0;
        vis[s]=1;
        while(!que.empty()){
            int cur=que.front();
            que.pop();
            for(int i=0;i<to[cur].size();i++){
                Edge& x=E[to[cur][i]];
                if(!vis[x.v]&&x.c>x.w){
                    vis[x.v]=1;
                    d[x.v]=d[cur]+1;
                    que.push(x.v);
                }
            }
        }
        return vis[t];
    }
    long long dfs(int u,long long v){
        if(u==t||v==0)
            return v;
        long long w=0,f;
        for(int i=C[u];i<to[u].size();i++){
            C[u]=i;
            Edge& e=E[to[u][i]];
            if(d[u]+1==d[e.v]&&(f=dfs(e.v,min(v,e.c-e.w)))>0){
                e.w+=f;
                E[to[u][i]^1].w-=f;
                w+=f;
                v-=f;
                if(v==0)
                    break;
            }
        }
        return w;
    }
    long long NativeMF(int s,int t){
        this->s=s;
        this->t=t;
        long long res=0;
        while(bfs()){
            memset(C,0,sizeof(C));
            res+=dfs(s,1e18);
        }
        return res;
    }
    long long Maxflow(int s,int t){
        long long ans[2]={},sum=0;
        for(int i=1;i<=n;i++){
            if(val[i]>0){
                NativeAE(N-2,i,val[i]);
                sum+=val[i];
            }
            if(val[i]<0)
                NativeAE(i,N-1,-val[i]);
        }
        NativeMF(N-2,N-1);
        NativeAE(t,s,1e16);
        NativeMF(N-2,N-1);
        return E[m-2].w;
    }
    void print(int p){
        if(p==2)
            return;
        if(p-2>0)
            printf("%d ",p-2);
        for(int i=0;i<to[p].size();i++){
            Edge &e=E[to[p][i]];
            if(e.w>0){
                e.w--;
                print(e.v);
                return;
            }
        }
    }
}R;
bool _(int u,int v){
    return R.E[u].v<R.E[v].v;
}
int n;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1,u;i<=n;i++){
        scanf("%d",&u);
        R.AddEdge(1,i+2,0,1e9);
        R.AddEdge(i+2,2,0,1e9);
        for(int j=1,v;j<=u;j++){
            scanf("%d",&v);
            R.AddEdge(i+2,v+2,1,1e9);
        }
    }
    for(int i=0;i<R.m;i++)
        sort(R.to[i].begin(),R.to[i].end(),_);
    printf("%lld\n",ans=R.Maxflow(1,2));
    for(int i=0;i<R.m;i++)
        R.E[i].w+=R.E[i].d;
    while(ans--){
        R.print(1);
        puts("");
    }
}/*

*/
2021/2/8 14:18
加载中...