网络流24题4

àì夳堔傛蜴生んèń 2022-01-10 03:13 184阅读 0赞

https://loj.ac/problem/6003

变化了下的最小路径覆盖，要注意边数巨多。。。

#include <iostream>
    #include <stdio.h>
    #include <queue>
    #include <cstring>
    using namespace std;
    int biao[100];
    const int maxn = 10009;
    int head[maxn];
    int cur[maxn];
    int tot = 0;
    struct edge{
        int v,nex,w;
    }e[maxn*20];
    void addedge(int u,int v,int w){
        e[tot] = (edge){v,head[u],w};
        head[u] = tot++;
        e[tot] = (edge){u,head[v],w};
        head[v] = tot++;
    }
    int deep[maxn];
    int nowball;
    bool bfs(int S,int T){
        for(int i=0;i<=2*nowball+1;i++){
            deep[i] = 0;
        }
        queue<int> q;
        deep[S] = 1;
        q.push(S);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(int i=head[now];i!=-1;i=e[i].nex){
                int v = e[i].v;
                int w = e[i].w;
                if(deep[v]!=0 || w<=0) continue;
                deep[v] = deep[now]+1;
                if(v==T) return deep[T];
                q.push(v);
            }
        }
        return deep[T];
    }
    int dfs(int now,int T,int maxflow){
        if(now==T) return maxflow;
        int all  =0;
        for(int &i=cur[now];i!=-1 &&all <maxflow;i=e[i].nex){
            int v = e[i].v;
            int w = e[i].w;
            if(deep[v]!=deep[now]+1 ||w<=0) continue;
            int tt = dfs(v,T,min(maxflow-all,w));
            e[i].w-=tt;
            e[i^1].w+=tt;
            all+=tt;
        }
        return all;
    }
    
    int dinic(int S,int T){
        int ret = 0;
        for(int i=0;i<=2*nowball+1;i++){
            cur[i] = head[i];
        }
        while(bfs(S,T)){
            ret+=dfs(S,T,0x3f3f3f3f);
            for(int i=0;i<=2*nowball;i++){
                cur[i] = head[i];
            }
        }
        return ret;
    }
    int vis[maxn*2];
    void  print(int now){
        if(now<=1 || now%2==1) return;
        vis[now] = 1;
        printf("%d ",now/2);
        for(int i=head[now];i!=-1;i=e[i].nex){
            int v = e[i].v;
            int w = e[i].w;
            if(w<=0){
                print(v^1);
            }
        }
    }
    int main()
    {
        for(int i=0;i<100;i++){
            biao[i] = i*i;
        }
        memset(head,-1,sizeof(head));
        int n;
        scanf("%d",&n);
        int kkk = 0;
        nowball = 0;
        while(true){
            nowball++;
            for(int i=0;i<100;i++){
                int from = biao[i]-nowball;
                if(from<1 || from>=nowball) continue;
                addedge(from*2,nowball*2+1,1);
            }
            addedge(0,nowball*2,1);
            addedge(nowball*2+1,1,1);
            kkk+=dinic(0,1);
            if(nowball-kkk<=n) continue;
            else{
                break;
            }
        }
        nowball--;
        printf("%d\n",nowball);
        for(int i=1;i<=nowball;i++){
            if(vis[2*i]==0) {
                print(2*i);
                printf("\n");
            }
    
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tjucxz/p/8562694.html