网络流

MCMF

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x3f3f3f3f;
int to[maxn<<1],cost[maxn<<1],cap[maxn<<1],flow[maxn<<1],nxt[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int c,int w){
    to[tot]=v;
    cap[tot]=c;
    flow[tot]=0;
    cost[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    cap[tot]=0;
    flow[tot]=0;
    cost[tot]=-w;
    nxt[tot]=head[u];
    head[u]=tot++;
}
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int x){que[rear++]=x;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;

int n,m,s,t;
bool vis[maxn];
int pre[maxn],dis[maxn];

bool spfa(){
    que.init();
    memset(vis,0,sizeof vis);
    memset(pre,0,sizeof pre);
    memset(dis,oo,sizeof dis);
    que.push(s);vis[s]=1;dis[s]=0;
    while(!que.empty()){
        int u=que.pop(); vis[u]=0;
        for(int i = head[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i],w=cost[i];
            if(c>f&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pre[v]=i;
                if(!vis[v]){
                    que.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(dis[t]==oo) return 0;
    else return 1;
}
int mc,mf;
void mcmf(){
    mc=mf=0;
    while(spfa()){
        int tf=oo+1;
        for(int i = pre[t]; ~i; i = pre[to[i^1]]){
            tf=min(tf,cap[i]-flow[i]);
        }
        mf+=tf;
        for(int i = pre[t]; ~i; i = pre[to[i^1]]){
            flow[i]+=tf;
            flow[i^1]-=tf;
        }
        mc+=dis[t]*tf;
    }
}
int main(){
    
}

来源:https://www.cnblogs.com/Missa/archive/2013/04/19/3030512.html
POJ2195 测试

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x3f3f3f3f;
int to[maxn<<1],cost[maxn<<1],cap[maxn<<1],flow[maxn<<1],nxt[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int c,int w){
    to[tot]=v;
    cap[tot]=c;
    flow[tot]=0;
    cost[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    cap[tot]=0;
    flow[tot]=0;
    cost[tot]=-w;
    nxt[tot]=head[u];
    head[u]=tot++;
}
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int x){que[rear++]=x;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
int n,m,s,t;
bool vis[maxn];
int pre[maxn],dis[maxn];
bool spfa(){
    que.init();
    memset(vis,0,sizeof vis);
    memset(pre,-1,sizeof pre);
    memset(dis,oo,sizeof dis);
    que.push(s);vis[s]=1;dis[s]=0;
    while(!que.empty()){
        int u=que.pop(); vis[u]=0;
        for(int i = head[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i],w=cost[i];
            if(c>f&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pre[v]=i;
                if(!vis[v]){
                    que.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(dis[t]==oo) return 0;
    else return 1;
}
int mc,mf;
void mcmf(){
    mc=mf=0;
    while(spfa()){
        int tf=oo+1;
        for(int i = pre[t]; ~i; i = pre[to[i^1]]){
            tf=min(tf,cap[i]-flow[i]);
        }
        mf+=tf;
        for(int i = pre[t]; ~i; i = pre[to[i^1]]){
            flow[i]+=tf;
            flow[i^1]-=tf;
        }
        mc+=dis[t]*tf;
    }
}
char G[233][233];
int main(){
    int row,col;
    while(scanf("%d%d",&row,&col)!=EOF){
        if(row==0) break;
        init();s=row*col+1;n=t=s+1;
        for(int i = 1; i <= row; i++){
            scanf("%s",G[i]+1);
        }
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                if(G[i][j]=='H') add((i-1)*col+j,t,1,0);
                else if(G[i][j]=='m') add(s,(i-1)*col+j,oo,0);
                if(G[i][j]=='.'||G[i][j]=='m'){
                    if(i-1>=1) add((i-1)*col+j,(i-2)*col+j,oo,1);
                    if(i+1<=row) add((i-1)*col+j,(i)*col+j,oo,1);
                    if(j-1>=1) add((i-1)*col+j,(i-1)*col+j-1,oo,1);
                    if(j+1<=col) add((i-1)*col+j,(i-1)*col+j+1,oo,1);
                }
            }
        }
        mcmf();
        printf("%d\n",mc);
    }
    return 0;
}

Dinic
HDU1532 模板测试

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+11;
const int oo = 1<<30;
struct Edge{
    int to,cap,rev;
};
int d[maxn],n,m;
vector<Edge> G[maxn];
void add(int u,int v,int w){
    G[u].push_back((Edge){v,w,G[v].size()});
    G[v].push_back((Edge){u,0,G[u].size()-1});
}
bool bfs(int s,int t){
    queue<int> q;
    while(!q.empty())q.pop();
    memset(d,-1,sizeof d);
    d[s]=0;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i].to;
            if(G[u][i].cap>0&&d[v]==-1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[t]!=-1;
}
int dfs(int u,int t,int micap){
    if(u==t)return micap;
    int tmp;
    for(int i = 0; i < G[u].size(); i++){
        Edge &e=G[u][i];
        if(e.cap>0&&d[u]+1==d[e.to]&&(tmp=dfs(e.to,t,min(e.cap,micap)))){
            e.cap-=tmp;
            G[e.to][e.rev].cap+=tmp;
            return tmp;
        }
    }
    return 0;
}
int dinic(int s,int t){
    int ans=0,tmp;
    while(bfs(s,t)){
        while(1){
            tmp=dfs(s,t,oo);
            if(tmp==0)break;
            ans+=tmp;
        }
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(G,0,sizeof G);
        int u,v,w;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        printf("%d\n",dinic(1,m));
    }
    return 0;
}

听说很厉害的ISAP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],val[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add1(int u,int v,int w){
    to[tot]=v;
    val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    val[tot]=0;//
    nxt[tot]=head[u];
    head[u]=tot++;
}
//void add2(int u,int v,int w){
//    to[tot]=v;
//    val[tot]=w;
//    nxt[tot]=head[u];
//    head[u]=tot++;
//    swap(u,v);
//    to[tot]=v;
//    val[tot]=w;
//    nxt[tot]=head[u];
//    head[u]=tot++;
//}
int n,m,s,t;
int dis[maxn],gap[maxn];
int dfs(int u,int cost){
    if(u==t)return cost;
    int mindis=n-1,lv=cost,d;
    for(int i=head[u];~i;i=nxt[i]){
        int v=to[i],w=val[i];
        if(w>0){
            if(dis[v]+1==dis[u]){
                d=min(lv,w);
                d=dfs(v,d);
                val[i]-=d;
                val[i^1]+=d;
                lv-=d;
                if(dis[s]>=n) return cost-lv;
                if(lv==0) break;
            }
            mindis=min(mindis,dis[v]);
        }
    }
    if(lv==cost){
        --gap[dis[u]];
        if(!gap[dis[u]]) dis[s]=n;
        dis[u]=mindis+1;
        ++gap[dis[u]];
    }
    return cost-lv;
}
int sap(int st,int ed){
    s=st,t=ed;
    int ans=0;
    memset(gap,0,sizeof gap);
    memset(dis,0,sizeof dis);
    gap[s]=n;
    while(dis[s]<n) ans+=dfs(s,oo);
    return ans;
}
int main(){
    while(scanf("%d%d",&m,&n)!=EOF){
        init();
        int u,v,w;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d",&u,&v,&w);
            add1(u,v,w);
        }
        printf("%d\n",sap(1,n));
    }
    return 0;
}

HDU4280
ISAP 3700ms+
Dinic TLE

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],pre[maxn],cur[maxn],gap[maxn];//pre 父边 
bool vis[maxn];
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
void bfs(){
    memset(vis,0,sizeof vis);
    que.init();
    que.push(t);
    vis[t]=1;dis[t]=0;
    while(que.empty()^1){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            register int v=to[i],c=cap[i^1],f=flow[i^1];
            if(!vis[v]&&c>f){
                vis[v]=1;
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
}
int aug(){
    int u=t,ans=oo;
    while(u!=s){
        ans=min(ans,cap[pre[u]]-flow[pre[u]]);
        u=to[pre[u]^1];
    }
    u=t;
    while(u!=s){
        flow[pre[u]]+=ans;
        flow[pre[u]^1]-=ans;
        u=to[pre[u]^1];
    }
    return ans;
}
int isap(){
    int ans=0;
    bfs();
    memset(gap,0,sizeof gap);
    memcpy(cur,head,sizeof head);
    for(int i = 1; i <= n; i++) gap[dis[i]]++;
    int u = s;
    //memset(cur,0,sizeof cur);
    while(dis[s]<n){
        if(u==t){
            ans+=aug();
            u=s;
        }
        bool ok=0;
        for(int i = cur[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i];
            if(c>f&&dis[u]==dis[v]+1){
                ok=1;
                pre[v]=i;
                cur[u]=i;
                u=v;
                break;
            }
        }
        if(!ok){
            int mn=n-1;
            for(int i = head[u]; ~i; i = nxt[i]){
                int v=to[i],c=cap[i],f=flow[i];
                if(c>f) mn=min(mn,dis[v]);
            }
            if(--gap[dis[u]]==0) break;
            dis[u]=mn+1;gap[dis[u]]++;cur[u]=head[u];
            if(u!=s) u=to[pre[u]^1];
        }
    }
    return ans;
}
int main(){
    int T,x,y,u,v,w; scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d",&n,&m);
        int mn=oo,mx=-oo;
        int mni=1,mxi=1;
        for(int i = 1; i <= n; i++){
            scanf("%d%d",&x,&y);
            if(x<mn){
                mn=x;
                mni=i;
            }
            if(x>mx){
                mx=x;
                mxi=i;
            }
        }
        s=mni,t=mxi;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        printf("%d\n",isap());
    }
    return 0;
}

网络流24题
luogu - P2756
自己写的BFS只得60+分,有部分重复匹配,感觉有点迷...
以后还是用人家的多路dfs版本吧//然而上面那题会T

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],gap[maxn];
int dfs(int u,int cc){
    if(u==t)return cc; 
    int mn=n-1,yue=cc,aug;
    for(int i = head[u]; ~i; i = nxt[i]){
        int v=to[i],c=cap[i],f=flow[i];
        if(c>f){
            if(dis[v]+1==dis[u]){
                aug=min(yue,c-f);
                aug=dfs(v,aug);
                flow[i]+=aug;
                flow[i^1]-=aug;
                yue-=aug;
                if(dis[s]>=n) return cc-yue;//delta
                if(yue==0) break;
            }
            mn=min(mn,dis[v]);
        }
    }
    if(yue==cc){
        --gap[dis[u]];
        if(gap[dis[u]]==0) dis[s]=n;
        dis[u]=mn+1;
        ++gap[dis[u]];
    }
    return cc-yue;
}
int isap(){
    int ans=0;
    memset(gap,0,sizeof gap);
    memset(dis,0,sizeof dis);
    gap[s]=n;
    while(dis[s]<n) ans+=dfs(s,oo);
    return ans;
}
int main(){
    int n1,n2;
    while(scanf("%d%d",&n2,&n)!=EOF){
        init();
        n+=2;
        s=0;t=n;
        for(int i = 1; i <= n2; i++){
            add(s,i,1);
        }
        for(int i = n2+1; i <= n-2; i++){
            add(i,t,1);
        }
        int u,v;
        while(scanf("%d%d",&u,&v)){
            if(u==v&&v==-1) break;
            add(u,v,1);
        }
        int ans=isap();
        if(ans==0)printf("No Solution!\n");
        else{
            printf("%d\n",ans);
            for(int i = 1; i <= n2; i++){
                for(int j = head[i]; ~j; j = nxt[j]){
                    if(flow[j]==1){
                        if(to[j]==0&&to[j]<=n2) continue;
                        printf("%d %d\n",i,to[j]);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

注意单向啊!!!

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],pre[maxn],cur[maxn],gap[maxn];
bool vis[maxn];
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
void bfs(){
    memset(vis,0,sizeof vis);
    que.init();
    que.push(t);
    vis[t]=1;dis[t]=0;
    while(que.empty()^1){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            register int v=to[i],c=cap[i^1],f=flow[i^1];
            if(!vis[v]&&c>f){
                vis[v]=1;
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
}
int aug(){
    int u=t,ans=oo;
    while(u!=s){
        ans=min(ans,cap[pre[u]]-flow[pre[u]]);
        u=to[pre[u]^1];
    }
    u=t;
    while(u!=s){
        flow[pre[u]]+=ans;
        flow[pre[u]^1]-=ans;
        u=to[pre[u]^1];
    }
    return ans;
}
int isap(){
    int ans=0;
    bfs();
    memset(gap,0,sizeof gap);
    memcpy(cur,head,sizeof head);
    for(int i = 1; i <= n; i++) gap[dis[i]]++;
    int u = s;
    while(dis[s]<n){
        if(u==t){
            ans+=aug();
            u=s;
        }
        bool ok=0;
        for(int i = cur[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i];
            if(c>f&&dis[u]==dis[v]+1){
                ok=1;
                pre[v]=i;
                cur[u]=i;
                u=v;
                break;
            }
        }
        if(!ok){
            int mn=n-1;
            for(int i = head[u]; ~i; i = nxt[i]){
                int v=to[i],c=cap[i],f=flow[i];
                if(c>f) mn=min(mn,dis[v]);
            }
            if(--gap[dis[u]]==0) break;
            dis[u]=mn+1;gap[dis[u]]++;cur[u]=head[u];
            if(u!=s) u=to[pre[u]^1];
        }
    }
    return ans;
}
int main(){
    int n1,n2;
    while(scanf("%d%d",&n2,&n)!=EOF){
        init();
        n+=2;
        s=n-1;t=n;
        for(int i = 1; i <= n2; i++){
            add(s,i,1);
        }
        for(int i = n2+1; i <= n-2; i++){
            add(i,t,1);
        }
        int u,v;
        while(scanf("%d%d",&u,&v)){
            if(u==v&&v==-1) break;
            add(u,v,1);
        }
        int ans=isap();
        if(ans==0)printf("No Solution!\n");
        else{
            printf("%d\n",ans);
//            set<int> ss; 
            for(int i = 1; i <= n2; i++){
                for(int j = head[i]; ~j; j = nxt[j]){
                    if(flow[j]>0){
                        if(to[j]==s||to[j]<=n2) continue;
                        printf("%d %d\n",i,to[j]);
//                        if(ss.count(to[j]))cout<<"%%%%%%%%%%"<<endl;
//                        ss.insert(to[j]);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

luogu - P2764
一个点对应一条路径
最小点独立=点数-最大匹配
Get到记录路径的方法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],pre[maxn],cur[maxn],gap[maxn];
bool vis[maxn];
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
void bfs(){
    memset(vis,0,sizeof vis);
    que.init();
    que.push(t);
    vis[t]=1;dis[t]=0;
    while(que.empty()^1){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            register int v=to[i],c=cap[i^1],f=flow[i^1];
            if(!vis[v]&&c>f){
                vis[v]=1;
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
}
int nxxt[maxn];
int aug(){
    int u=t,ans=oo;
    while(u!=s){
        ans=min(ans,cap[pre[u]]-flow[pre[u]]);
        //*************************************************
        nxxt[to[pre[u]^1]]=u;//NOTE
        //*************************************************
        u=to[pre[u]^1];
    }
    u=t;
    while(u!=s){
        flow[pre[u]]+=ans;
        flow[pre[u]^1]-=ans;
        u=to[pre[u]^1];
    }
    return ans;
}
int isap(){
    int ans=0;
    bfs();
    memset(gap,0,sizeof gap);
    memcpy(cur,head,sizeof head);
    for(int i = 1; i <= n; i++) gap[dis[i]]++;
    int u = s;
    while(dis[s]<n){
        if(u==t){
            ans+=aug();
            u=s;
        }
        bool ok=0;
        for(int i = cur[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i];
            if(c>f&&dis[u]==dis[v]+1){
                ok=1;
                pre[v]=i;
                cur[u]=i;
                u=v;
                break;
            }
        }
        if(!ok){
            int mn=n-1;
            for(int i = head[u]; ~i; i = nxt[i]){
                int v=to[i],c=cap[i],f=flow[i];
                if(c>f) mn=min(mn,dis[v]);
            }
            if(--gap[dis[u]]==0) break;
            dis[u]=mn+1;gap[dis[u]]++;cur[u]=head[u];
            if(u!=s) u=to[pre[u]^1];
        }
    }
    return ans;
}
vector<int> G[maxn];
int main(){
    int n1,u,v;bool vis2[maxn];
    while(scanf("%d%d",&n1,&m)!=EOF){
        init();
        memset(nxxt,0,sizeof nxxt);
        n=2*n1+2;
        s=n-1;t=n;
        for(int i = 1; i <= n1; i++){
            add(s,i,1);
            add(i+n1,t,1);
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d",&u,&v);
            add(u,v+n1,1);
        }
        int ans = n1-isap();
        memset(vis2,0,sizeof vis2);
        for(int i = 1; i <= n1; i++) G[i].clear();
        //*************************************************
        for(int i = 1; i <= n1; i++){
            if(!vis2[i]){
                for(int j = i; j; j=nxxt[j]){
                    if(j>n1)j-=n1;
                    G[i].push_back(j);
                    vis2[j]=1;
                }
            }
        }
        
        for(int i = 1; i <= n1; i++){
            if(G[i].size()==0)continue;
            for(int j = 0; j < G[i].size(); j++){
                if(j==G[i].size()-1)printf("%d\n",G[i][j]);
                else printf("%d ",G[i][j]);
            }
        }
        //*************************************************
        printf("%d\n",ans);
    }
    return 0;
}

luogu - P2762

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],pre[maxn],cur[maxn],gap[maxn];
bool vis[maxn];
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
void bfs(){
    memset(vis,0,sizeof vis);
    que.init();
    que.push(t);
    vis[t]=1;dis[t]=0;
    while(que.empty()^1){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            register int v=to[i],c=cap[i^1],f=flow[i^1];
            if(!vis[v]&&c>f){
                vis[v]=1;
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
}
int nxxt[maxn];
int aug(){
    int u=t,ans=oo;
    while(u!=s){
        ans=min(ans,cap[pre[u]]-flow[pre[u]]);
        //*************************************************
//        nxxt[to[pre[u]^1]]=u;//NOTE
        u=to[pre[u]^1];
    }
    u=t;
    while(u!=s){
        flow[pre[u]]+=ans;
        flow[pre[u]^1]-=ans;
        u=to[pre[u]^1];
    }
    return ans;
}
int isap(){
    int ans=0;
    bfs();
    memset(gap,0,sizeof gap);
    memcpy(cur,head,sizeof head);
    for(int i = 1; i <= n; i++) gap[dis[i]]++;
    int u = s;
    while(dis[s]<n){
        if(u==t){
            ans+=aug();
            u=s;
        }
        bool ok=0;
        for(int i = cur[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i];
            if(c>f&&dis[u]==dis[v]+1){
                ok=1;
                pre[v]=i;
                cur[u]=i;
                u=v;
                break;
            }
        }
        if(!ok){
            int mn=n-1;
            for(int i = head[u]; ~i; i = nxt[i]){
                int v=to[i],c=cap[i],f=flow[i];
                if(c>f) mn=min(mn,dis[v]);
            }
            if(--gap[dis[u]]==0) break;
            dis[u]=mn+1;gap[dis[u]]++;cur[u]=head[u];
            if(u!=s) u=to[pre[u]^1];
        }
    }
    return ans;
}
int label[maxn];
//*********************************************************************************
void dfs(int u){
    label[u]=1;
    for(int i = head[u]; ~i; i = nxt[i]){
        int v = to[i],c=cap[i],f=flow[i];
        if(!label[v]&&c>f)dfs(v);
    }
}
//*********************************************************************************
vector<int> G[maxn];
int main(){
    int n1,n2,u,v,w,c,f,x,sum,ans;
    while(scanf("%d%d",&n1,&n2)!=EOF){
        init();sum=0;
        s=n1+n2+1;t=s+1;n=t;
        for(int i = 1; i <= n1; i++){
            scanf("%d",&x);sum+=x;
            add(s,i,x);
            char ch=getchar();
            int x = 0;
            while((ch=getchar())!='\n'){
                if(ch>='0'&&ch<='9') x=x*10+ch-'0';
                if(ch==' ')add(i,x+n1,oo),x=0;
            }
            if(x) add(i,x+n1,oo);
        }
        for(int i = 1; i <= n2; i++){
            scanf("%d",&x);
            add(i+n1,t,x);
        }
        int tt=isap();
        //*********************************************************************************
        dfs(s);
        for(int i = 1; i <= n1; i++) if(label[i]==label[s])printf("%d ",i);printf("\n");
        for(int i = 1; i <= n2; i++) if(label[i+n1]!=label[t])printf("%d ",i);printf("\n");
        //*********************************************************************************
        printf("%d\n",sum-tt);
    }
    return 0;
}

圆桌问题
从输出来看应该是对的
不过没有完善的Special Judge支持验证

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int dis[maxn],pre[maxn],cur[maxn],gap[maxn];
bool vis[maxn];
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
void bfs(){
    memset(vis,0,sizeof vis);
    que.init();
    que.push(t);
    vis[t]=1;dis[t]=0;
    while(que.empty()^1){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            register int v=to[i],c=cap[i^1],f=flow[i^1];
            if(!vis[v]&&c>f){
                vis[v]=1;
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
}
int nxxt[maxn];
int aug(){
    int u=t,ans=oo;
    while(u!=s){
        ans=min(ans,cap[pre[u]]-flow[pre[u]]);
        u=to[pre[u]^1];
    }
    u=t;
    while(u!=s){
        flow[pre[u]]+=ans;
        flow[pre[u]^1]-=ans;
        u=to[pre[u]^1];
    }
    return ans;
}
int isap(){
    int ans=0;
    bfs();
    memset(gap,0,sizeof gap);
    memcpy(cur,head,sizeof head);
    for(int i = 1; i <= n; i++) gap[dis[i]]++;
    int u = s;
    while(dis[s]<n){
        if(u==t){
            ans+=aug();
            u=s;
        }
        bool ok=0;
        for(int i = cur[u]; ~i; i = nxt[i]){
            int v=to[i],c=cap[i],f=flow[i];
            if(c>f&&dis[u]==dis[v]+1){
                ok=1;
                pre[v]=i;
                cur[u]=i;
                u=v;
                break;
            }
        }
        if(!ok){
            int mn=n-1;
            for(int i = head[u]; ~i; i = nxt[i]){
                int v=to[i],c=cap[i],f=flow[i];
                if(c>f) mn=min(mn,dis[v]);
            }
            if(--gap[dis[u]]==0) break;
            dis[u]=mn+1;gap[dis[u]]++;cur[u]=head[u];
            if(u!=s) u=to[pre[u]^1];
        }
    }
    return ans;
}
int main(){
    int n1,n2,u,v,w,c,f,x;
    while(scanf("%d%d",&n1,&n2)==2){//桌子 单位 
        if(n1==0)break;
        init();
        s=n1+n2+1;t=s+1;n=t;
        for(int i = 1; i <= n1; i++){
            scanf("%d",&x);
            add(i+n2,t,x);
        }
        for(int i = 1; i <= n2; i++){
            scanf("%d",&x);
            add(s,i,x);
            for(int j = 1; j <= n1; j++) add(i,j+n2,1);
        }
        printf("%d\n",isap()?1:0);
        for(int i = 1; i <= n2; i++){
            stack<int> stk;
            for(int j = head[i]; ~j; j = nxt[j]){
                int v=to[j],c=cap[j^1],f=flow[j^1];//?
                if(c-f>0&&!(j&1))stk.push(v-n2);
            }
            while(!stk.empty()){
                if(stk.size()==1){printf("%d\n",stk.top());stk.pop();}
                else {printf("%d ",stk.top());stk.pop();};
            }
        }
    }
    return 0;
}

luogu - P2763
依然A不了啊,spj能不能用心点//从黑箱数据来看是对的是对的是对的!
手速宏真好啊
PS.这道题要是求方案数那该咋办啊?求菊苣解释

#define scan(a) scanf("%d",&(a))
#define scann(a,b) scanf("%d%d",&(a),&(b)) 
#define rep(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define rep0(i,n) for(int (i)=0;(i)<(n);(i)++)
#define print(a) printf("%d\n",(a))
#define erep(i,u) for(int (i)=head[(u)];~(i);(i)=nxt[(i)])
vector<int> G[2333];
int main(){
    int n1,n2,u,v,w,c,f,ans,x,sum;
    while(scann(n1,n2)!=EOF){
        init();s=n1+n2+1;n=t=s+1;
        rep(i,n1){
            scan(x);
            add(i+n2,t,x);
        }
        rep(i,n2){
            scan(x);
            add(s,i,x);
            rep(j,x){
                scan(w);
                add(i,w+n2,1);
            }
        }
        ans=isap();
//        cout<<"ans:"<<ans<<endl;
        if(ans==0){
            printf("No Solution!\n");
            continue;
        }
        rep0(i,2333)G[i].clear();
//        rep(i,n1){
//            erep(j,i){
//                v=to[j],c=cap[j^1],f=flow[j^1];//^1 not a universal rev edge 
//                printf("i:%d V:%d C:%d F:%d\n",i,v,c,f);
//            }
//        }
        rep(i,n2){
            erep(j,i){
                v=to[j],c=cap[j],f=flow[j];
                if(v>n2&&c==f) G[v-n2].push_back(i);
            } 
        }
        rep(i,n1){
            if(G[i].size())printf("%d: ",i);
            rep0(j,G[i].size()){
                if(j==G[i].size()-1)print(G[i][j]);
                else printf("%d ",G[i][j]);
            }
        }
    }
    return 0;
} 

luogu - P2766
不错的分析:上述建模方法是应用了一种分层图的思想,把图每个顶点i按照F[i]的不同分为了若干层,这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出,需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数,所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可。

int a[maxn],dp[maxn];int n1,u,v,w,c,f,x,ans,sum;
int LIS(){
    for(int i = 1; i <= n1; i++) dp[i]=1;dp[0]=0;
    for(int i = 1; i <= n1; i++){
        for(int j = 1; j < i; j++){
            if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);
        }
    }
    int mx=-oo;for(int i = 1; i <= n1; i++)mx=max(mx,dp[i]);
    return mx;
}
int main(){
    while(scanf("%d",&n1)!=EOF){
        init();
        for(int i = 1; i <= n1; i++){
            scanf("%d",&a[i]);
        }
        int mx=LIS();
        printf("%d\n",mx);
        bool flag=0;
        if(mx==1) flag=1;
        s=2*n1+1;t=s+1;n=t; 
        for(int i = 1; i <= n1; i++){
            add(i,i+n1,1);//NOTE:自己跑自己一定可以 
            if(dp[i]==mx) add(i+n1,t,1); 
            if(dp[i]==1) add(s,i,1);
        }
        for(int i = 1; i <= n1; i++){
            for(int j = i+1; j <= n1; j++){
                if(a[i]<=a[j]&&dp[j]==dp[i]+1) add(i+n1,j,1);
            }
        }
        printf("%d\n",isap());
        init();
        for(int i = 1; i <= n1; i++){
            if(i==1||i==n1) add(i,i+n1,oo); 
            else add(i,i+n1,1);
            if(dp[i]==mx) { if(i==n1)add(i+n1,t,oo); else add(i+n1,t,1); }
            if(dp[i]==1) { if(i==1)add(s,i,oo); else add(s,i,1);}
        }
        for(int i = 1; i <= n1; i++){
            for(int j = i+1; j <= n1; j++){
                if(a[i]<=a[j]&&dp[j]==dp[i]+1) add(i+n1,j,1);
            }
        }
        printf("%d\n",isap());
    }
    return 0;
}

luogu - P2774
建模细节很重要
黑白染色

int n1,u,v,w,c,f,x,ans,sum,row,col,cnt;
int a[123][123],mark[123][123];
int main(){
    while(scanf("%d%d",&row,&col)!=EOF){
        init();sum=cnt=0;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                scanf("%d",&x);a[i][j]=x;mark[i][j]=++cnt;
                sum+=x;
            }
        } 
        s=2*cnt+1;t=s+1;n=t;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                if(i+j&1)add(s,mark[i][j],a[i][j]);
                else add(mark[i][j]+cnt,t,a[i][j]);
            }
        }
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++)if(i+j&1){
                if(i-1>=1) add(mark[i][j],mark[i-1][j]+cnt,oo);
                if(i+1<=row) add(mark[i][j],mark[i+1][j]+cnt,oo);
                if(j-1>=1) add(mark[i][j],mark[i][j-1]+cnt,oo);
                if(j+1<=col) add(mark[i][j],mark[i][j+1]+cnt,oo);
            }            
        }
        printf("%d\n",sum-isap());
    }
    return 0;
}

围观dalao:http://www.cnblogs.com/DragoonKiller/p/4295953.html
dalao2:http://blog.csdn.net/Lcomyn/article/details/43636873
dalao3:https://www.cnblogs.com/owenyu/p/6852664.html
dalao4:https://www.cnblogs.com/georgechen-ena/archive/2011/11/07/2240185.html
dalao5:http://blog.csdn.net/orzgeotcbrl/article/details/50808548

POJ3281
注意V必须在1...n范围内
想了一下牛为什么要拆点,毕竟边容量都是1感觉没可能要拆啊
后来发现这个显然的道理感觉自己的推断能力真是渣的一塌糊涂,
点权和边权是显然不同的,多个1的边权就等价于大于1的点权,WA的理所当然啊
所以显然需要拆点来限制点权

int main(){
    int N,F,D,fi,di,x;
    while(scanf("%d%d%d",&N,&F,&D)!=EOF){
        init();n=2*N+F+D+2;s=n-1;t=s+1;
        int cow=F,cow2=F+N,drink=F+2*N;
        for(int i = 1; i <= F; i++) add(s,i,1);
        for(int i = 1; i <= D; i++) add(i+drink,t,1);
        for(int i = 1; i <= N; i++) add(i+cow,i+cow2,1);
        for(int i = 1; i <= N; i++){
            scanf("%d%d",&fi,&di);
            for(int j = 1; j <= fi; j++){
                scanf("%d",&x);
                add(x,i+cow,1);
            }
            for(int j = 1; j <= di; j++){
                scanf("%d",&x);
                add(i+cow2,x+drink,1);
            }
        }
        printf("%d\n",isap());
    }
    return 0;
} 

ISAP2.0
之前使用的版本在CF546E中突然WA了无数发,然而和市面上的比较好像也没啥大问题..
先换了再说
AC版本

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> 
#include<queue>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x3f3f3f3f;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=0;
    flow[tot]=0;
    head[u]=tot++;
}
struct QUEUE{
    int que[maxn];
    int front,rear;
    void init(){front=rear=0;}
    void push(int u){que[rear++]=u;}
    int pop(){return que[front++];}
    bool empty(){return front==rear;}
}que;
int n,m,s,t;
int gap[maxn],dep[maxn];
void bfs(){
    memset(dep,-1,sizeof dep);
    memset(gap,0,sizeof gap);
    gap[0]=1;
    que.init();
    que.push(t);dep[t]=0;
    while(!que.empty()){
        int u = que.pop();
        for(int i = head[u]; ~i; i = nxt[i]){
            int v=to[i];
            if(~dep[v])continue;
            que.push(v);
            dep[v]=dep[u]+1;
            gap[dep[v]]++;
        }
    }    
}
int cur[maxn],S[maxn];
int isap(){
    bfs();
    memcpy(cur,head,sizeof head);
    int ans=0,top=0,u=s;
    while(dep[s]<n){
        if(u==t){
            int mn=oo;
            int inser;
            for(int i = 0; i < top; i++){
                if(mn>cap[S[i]]-flow[S[i]]){
                    mn=cap[S[i]]-flow[S[i]];
                    inser=i;
                }
            }
            for(int i = 0; i < top; i++){
                flow[S[i]]+=mn;
                flow[S[i]^1]-=mn;
            }
            ans+=mn;
            top=inser;
            u=to[S[top]^1];
            continue;
        }
        bool flag=0;
        int v;
        for(int i = cur[u]; ~i; i = nxt[i]){
            v=to[i];
            if(cap[i]-flow[i]&&dep[v]+1==dep[u]){
                flag=1;
                cur[u]=i;
                break;
            }
        }
        if(flag){
            S[top++]=cur[u];
            u=v;
            continue;
        }
        int mn=n;
        for(int i = head[u]; ~i; i = nxt[i]){
            if(cap[i]-flow[i]&&dep[to[i]]<mn){
                mn=dep[to[i]];
                cur[u]=i;
            }
        }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u]=mn+1;
        gap[dep[u]]++;
        if(u!=s)u=to[S[--top]^1];
    }
    return ans;
}
int G[122][122];
int main(){
    int n1,ans,sum1,sum2,u,v;
    int a[maxn],b[maxn];
    while(scanf("%d%d",&n1,&m)!=EOF){
        init();sum1=sum2=0;
        n=2*n1+2;s=n-1;t=n;
        for(int i = 1; i <= n1; i++) {scanf("%d",&a[i]);sum1+=a[i];add(s,i,a[i]);}
        for(int i = 1; i <= n1; i++) {scanf("%d",&b[i]);sum2+=b[i];add(i+n1,t,b[i]);}
        for(int i = 1 ;i <= n1; i++) add(i,i+n1,oo);
        for(int i = 1; i <= m; i++){
            scanf("%d%d",&u,&v);
            add(u,v+n1,oo);
            add(v,u+n1,oo);
        }
        if(sum1!=sum2) printf("NO\n");
        else if(isap()!=sum2) printf("NO\n");
        else{
            printf("YES\n");
            memset(G,0,sizeof G);
            for(int i = 1; i <= n1; i++){
                for(int j = head[i]; ~j; j = nxt[j]){
                    int v=to[j],f=flow[j];
                    if(f>0&&v!=s)G[i][v-n1]=f;
                }
            }
            for(int i = 1; i <= n1; i++){
                for(int j = 1; j <= n1; j++){
                    if(j==n1) printf("%d\n",G[i][j]);
                    else printf("%d ",G[i][j]);
                }
            }
        } 
    }
    return 0;
} 

裸的

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x7fffffff;
int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1];
int head[maxn],tot;
void init(){
    memset(head,-1,sizeof head);
    tot=0;
}
void add(int u,int v,int w){
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
    swap(u,v);
    to[tot]=v;
    nxt[tot]=head[u];
    cap[tot]=w;
    flow[tot]=0;
    head[u]=tot++;
}
int n,m,s,t;
int gap[maxn],dep[maxn],que[maxn];
int cur[maxn],stk[maxn];
void bfs(){
    memset(dep,-1,sizeof dep);
    memset(gap,0,sizeof gap);
    gap[0]=1;
    int front=0,rear=0;
    que[rear++]=t;dep[t]=0;
    while(front^rear){
        int u = que[front++];
        for(int i = head[u]; ~i; i = nxt[i]){
            int v=to[i];
            if(~dep[v])continue;
            que[rear++]=v;
            dep[v]=dep[u]+1;
            gap[dep[v]]++;
        }
    }    
}
int isap(){
    bfs();
    memcpy(cur,head,sizeof head);
    int ans=0,top=0,u=s;
    while(dep[s]<n){
        if(u==t){
            int mn=oo;
            int inser;
            for(int i = 0; i < top; i++){
                if(mn>cap[stk[i]]-flow[stk[i]]){
                    mn=cap[stk[i]]-flow[stk[i]];
                    inser=i;
                }
            }
            for(int i = 0; i < top; i++){
                flow[stk[i]]+=mn;
                flow[stk[i]^1]-=mn;
            }
            ans+=mn;
            top=inser;
            u=to[stk[top]^1];
            continue;
        }
        bool flag=0;
        int v;
        for(int i = cur[u]; ~i; i = nxt[i]){
            v=to[i];
            if(cap[i]-flow[i]&&dep[v]+1==dep[u]){
                flag=1;
                cur[u]=i;
                break;
            }
        }
        if(flag){
            stk[top++]=cur[u];
            u=v;
            continue;
        }
        int mn=n;
        for(int i = head[u]; ~i; i = nxt[i]){
            if(cap[i]-flow[i]&&dep[to[i]]<mn){
                mn=dep[to[i]];
                cur[u]=i;
            }
        }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u]=mn+1;
        gap[dep[u]]++;
        if(u!=s)u=to[stk[--top]^1];
    }
    return ans;
}

标签: 算法, 学习

添加新评论