上下界网络流的一些理解

周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧,转变成无源汇可行流问题
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉。从s到t求最大流,(网上说要去掉附加源汇ss,tt,其实我感觉不用去,因为ss和tt间没边,所以必要弧不可能退流,个人理解,正确性有待检验)
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加,求ss到tt的最大流ans2
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且的流量就是最小流,否则无解
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0

上下界网络流专题

各种流的一句话总结,相当经典:http://blog.csdn.net/pouy94/article/details/6628521
zoj 2314 Reactor Cooling
无源汇可行流

#include<stdio.h>
#include<string.h>
#define maxn 210
#define maxe 100000+10
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int to;
    int next;
    int num;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,cnt,n,m;
int c[maxn],d[maxn];
int in[maxn],out[maxn],sum;
int ans[maxe],initc[maxe],initb[maxe];
inline int min(int a,int b) {return a<b?a:b;}
void add(int u,int v,int c,int num)
{
    edge[cnt].num=num;edge[cnt].c=c;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].num=num;edge[cnt].c=0;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
void init()
{
    sum=cnt=0;memset(head,-1,sizeof(int)*(n+10));
    memset(in,0,sizeof(int)*(n+10));
    memset(out,0,sizeof(int)*(n+10));
    return;
}
int dfs(int cur,int flow)
{
    if(cur==t) return flow;
    int res=0;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to,c=edge[i].c;
        if(c && d[cur]==d[v]+1)
        {
            int delta=dfs(v,min(flow,c));
            edge[i].c-=delta;edge[i^1].c+=delta;
            flow-=delta;res+=delta;
            if(!flow) break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(!c[d[cur]]) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(c,0,sizeof(int)*(n+10));
    memset(d,0,sizeof(int)*(n+10));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
void build()
{
    int i,cc=m;
    for(i=1;i<=n;i++)
    {
        int M=in[i]-out[i];
        if(M>=0) {add(s,i,M,++cc);sum+=M;}
        else add(i,t,-M,++cc);
    }
    n=t+1;
}
bool solve()
{
    build();
    if(sap()==sum) return 1;
    return 0;
}
int main()
{
    int i,j,T;
    int u,v,b,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        s=0;t=n+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&b,&c);
            in[v]+=b;out[u]+=b;
            add(u,v,c-b,i);
            initc[i]=c;initb[i]=b;
        }
        int cc=cnt;
        if(!solve()) {printf("NO\n");if(T!=0) printf("\n");}
        else
        {
            printf("YES\n");
            for(i=0;i<=cc-1;i+=2)
            {
                ans[edge[i].num]=initc[edge[i].num]-edge[i].c;
            }
            for(i=1;i<=m;i++) printf("%d\n",ans[i]);
            if(T!=0) printf("\n");
        }




    }

    return 0;
}

poj2396 && zoj1994 Budget
无源汇可行流

#include<stdio.h>
#include<string.h>
#define maxn 300
#define maxe 100000
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int cap[maxe];
int head[maxn];
int s,t,cnt,n,m;
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int in[maxn],out[maxn],sum;
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
void add(int u,int v,int c)
{
    edge[cnt].c=c;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].c=0;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
void init()
{
    sum=cnt=0;memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int low[210][30],high[210][30];
int row[210],col[30],all;
void cal(int r,int c,char type,int sum)
{
    int i,j;
    if(r==0 && c==0)
    {
        if(type=='<')
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                    high[i][j]=min(high[i][j],sum-1);
        }
        else if(type=='>')
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                    low[i][j]=max(low[i][j],sum+1);
        }
        else
        {
            for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
                {
                    high[i][j]=min(high[i][j],sum);
                    low[i][j]=max(low[i][j],sum);
                }
        }
    }
    else if(r==0 && c!=0)
    {
        if(type=='<')
            for(i=1;i<=n;i++) high[i]1=min(high[i]1,sum-1);
        else if(type=='>')
            for(i=1;i<=n;i++) low[i]1=max(low[i]1,sum+1);
        else
        for(i=1;i<=n;i++) {high[i]1=min(high[i]1,sum);low[i]1=max(low[i]1,sum);}
    }
    else if(c==0 && r!=0)
    {
        if(type=='<')
            for(i=1;i<=m;i++) high[r][i]=min(high[r][i],sum-1);
        else if(type=='>')
            for(i=1;i<=m;i++) low[r][i]=max(low[r][i],sum+1);
        else
        for(i=1;i<=m;i++) {high[r][i]=min(high[r][i],sum);low[r][i]=max(low[r][i],sum);}
    }
    else
    {
        if(type=='<') high[r]1=min(high[r]1,sum-1);
        else if(type=='>')low[r]1=max(low[r]1,sum+1);
        else { high[r]1=min(high[r]1,sum);low[r]1=max(low[r]1,sum); }
    }
    return;
}
int main()
{
    int i,j,T;
    int u,v,b,c,tmp;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(low,0,sizeof(low));
        memset(high,inf,sizeof(high));
        memset(row,0,sizeof(row));memset(col,0,sizeof(col));
        init();
        s=0;t=n+m+1;int ss=t+1;int tt=ss+1;
        all=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&row[i]);all+=row[i];
            add(s,i,row[i]);
        }
        for(i=n+1;i<=n+m;i++)
        {
            scanf("%d",&col[i-n]);
            add(i,t,col[i-n]);
        }
        add(t,s,0);in[s]+=all;out[t]+=all;
        int cn;char str[5];
        bool flag=1;
        scanf("%d",&cn);
        while(cn--)
        {
            scanf("%d%d%s%d",&i,&j,str,&tmp);
            cal(i,j,str[0],tmp);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                if(low[i][j]>high[i][j]) {flag=0;break;}
            if(!flag) break;
        }
        if(!flag) {printf("IMPOSSIBLE\n");if(T!=0) printf("\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                cap[cnt]=high[i][j];add(i,n+j,high[i][j]-low[i][j]);
                in[n+j]+=low[i][j];out[i]+=low[i][j];
            }
        for(i=s;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans=isap(ss,tt,tt+1);
        if(ans!=sum) {printf("IMPOSSIBLE\n");if(T!=0) printf("\n");continue;}
        for(i=1;i<=n;i++)
        {
            for(j=head[i];j!=-1;j=edge[j].next)
            {
                if(j&1) continue;
                low[i][edge[j].to-n]=cap[j]-edge[j].c;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                printf("%d",low[i][j]);
                if(j!=m) printf(" ");
            }
            printf("\n");
        }
        if(T!=0) printf("\n");
    }
    return 0;
}

poj2594 Treasure Exploration
解法一:DAG最小可相交路径覆盖:先求佛洛依德传递闭包,再求不相交最小路径覆盖

#include<stdio.h>
#include<string.h>
#define maxn 1000+10
#define maxe 250000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m,cnt;
int match[maxn];
bool use[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(use,0,sizeof(bool)*(2*n+10));
        if(match[i]) continue;
        if(dfs(i)) ans++;
    }
    return ans;
}
bool map[510][510];
int main()
{
    int i,j,k;
    int u,v;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) map[i][j]=(i==j);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            map[u][v]=1;
        }
        for(k=1;k<=n;k++)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                {
                    map[i][j]|=(map[i][k] && map[k][j]);
                }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j) continue;
                if(map[i][j]) add(i,n+j);
            }
        printf("%d\n",n-xyl());
    }


    return 0;
}

hdoj3157 Crazy Circuits
上下界最小流

#include<stdio.h>
#include<string.h>
#include <queue>
#define maxn 60
#define maxe 610
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge
{
    int c,from,to,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt;
int s,t;
inline void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
void scan(int &num)//对G++使用
{
    char in;
    while(((in=getchar()) > '9' || in<'0') && in!='-' && in!='+');
    if(in=='-' || in=='+')
    {
        if(in=='-') num=t;
        if(in=='+') num=s;
        return;
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    return;
}
int in[maxn],out[maxn];
int main()
{
    int i,j;
    int n,m;
    int u,v,c;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        s=0;t=n+1;
        for(i=1;i<=m;i++)
        {
            scan(u);scan(v);scan(c);
            out[u]+=c;in[v]+=c;
            add(u,v,inf-c);
        }
        int ss=t+1,tt=ss+1,sum=0;
        for(i=0;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans1=isap(ss,tt,tt+1);
        add(t,s,inf);
        int ans2=isap(ss,tt,tt+1);
        if(ans1+ans2!=sum) printf("impossible\n");
        else printf("%d\n",edge[cnt-1].c);
    }
    return 0;
}

SGU176 Flow construction
上下界最小流

#include<stdio.h>
#include<string.h>
#include <queue>
#define maxn 110
#define maxe 50010
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge
{
    int from,to,c;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt,n,m,s,t;
int in[maxn],out[maxn];
int low[maxe];
inline void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=min(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int main()
{
    int i,j;
    int u,v,c,flag;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        memset(low,0,sizeof(low));
        s=1;t=n;
        int ss=n+1,tt=ss+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&c,&flag);
            if(flag) {in[v]+=c;out[u]+=c;low[cnt]=c;add(u,v,0);}
            else add(u,v,c);
        }
        int sum=0;
        for(i=1;i<=n;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) {add(ss,i,M);sum+=M;}
            else add(i,tt,-M);
        }
        int ans1=isap(ss,tt,tt);
        add(t,s,inf);
        int ans2=isap(ss,tt,tt);
        if(ans1+ans2!=sum) {printf("Impossible\n");continue;}
        printf("%d\n",edge[cnt-1].c);
        bool p=1;
        for(i=0;i<=2*m-2;i+=2)
        {
            if(!p) printf(" ");
            else p=0;
            printf("%d",low[i]+edge[i^1].c);
        }
        printf("\n");


    }
    return 0;
}

zoj 3229 Shoot the Bullet
裸的上下界最大流水题,数组开小了,折磨了好几天,按题意明明点数组400够用的。。

#include<stdio.h>
#include<string.h>
#define maxn 4000
#define maxe 368000
#define inf 1000000000
typedef struct Edge
{
    int from,to,c,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int gap[maxn],d[maxn],curedge[maxn],pre[maxn];
int cnt;
inline int minx(int a,int b){return a<b?a:b;}
void add(int u,int v,int c)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int isap(int s,int t,int n)
{
    int cur_flow,flow_ans=0,u,tmp,neck,i,v;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<n;i++)
        curedge[i]=head[i];
    gap[0]=n;
    u=s;
    while(d[s]<n)
    {
        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                if(cur_flow>edge[curedge[i]].c)
                {
                    neck=i;
                    cur_flow=edge[curedge[i]].c;
                }
            }
            for(i=s;i!=t;i=edge[curedge[i]].to)
            {
                tmp=curedge[i];
                edge[tmp].c-=cur_flow;
                edge[tmp^1].c+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].c && d[u]==d[v]+1)
                break;
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[v]=u;
            u=v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=head[u];
            for(tmp=n+5,i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].c)
                    tmp=minx(tmp,d[edge[i].to]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;
}
int low[maxe],in[maxn],out[maxn];
int dd[maxn];
int main()
{
    int i,j;
    int n,m,tmp;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));memset(out,0,sizeof(out));
        int s=0,t=n+m+1,ss=t+1,tt=ss+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&tmp);
            add(n+i,t,inf-tmp);
            in[t]+=tmp;out[n+i]+=tmp;
        }
        int start=cnt,end;
        for(i=1;i<=n;i++)
        {
            int cn,D;
            scanf("%d%d",&cn,&D);dd[i]=D;
            for(j=1;j<=cn;j++)
            {
                int tar,high,l;
                scanf("%d%d%d",&tar,&l,&high);
                low[cnt]=l;
                add(i,n+tar+1,high-l);
                out[i]+=l;in[n+tar+1]+=l;
            }
        }
        end=cnt;
        for(i=1;i<=n;i++) add(s,i,dd[i]);
        int sum=0;
        for(i=s;i<=t;i++)
        {
            int M=in[i]-out[i];
            if(M>=0) add(ss,i,M),sum+=M;
            else add(i,tt,-M);
        }
        add(t,s,inf);
        int ans1=isap(ss,tt,tt+1);
        if(ans1!=sum) {printf("-1\n\n");continue;}
        edge[cnt-1].c=edge[cnt-2].c=0;
        int ans2=isap(s,t,tt+1);
        printf("%d\n",ans1+ans2);
        for(i=start;i<=end-1;i++)
        {
            if(i&1) continue;
            int v=edge[i].to;
            if(n+1<=v && v<=n+m)
                printf("%d\n",low[i]+edge[i^1].c);

        }
        printf("\n");
    }

    return 0;
}

哈密顿回路存在性判断的一些充分条件

(已会)1.Dirac定理:无向图共n个顶点,每个顶点的度数均>=ceil(n/2),则该图一定含有哈密顿回路

(3的充分条件)

2.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n-1,则G一定存在哈密顿路

(已会)3.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n,则G一定存在哈密顿回路(Dirac定理的必要条件)

(已会)4.竞赛图一定有哈密顿路

5.竞赛图含有哈密顿回路当且仅当该竞赛图强连通

1.3的解决方法一样的,因为1和3本质相同,1比3条件强一些而已

hdoj4565 So Easy!

矩阵题,2013长沙邀请赛的题,但是貌似oj没有题目重现的比赛,没做到,结果长沙online居然出现了一道同一类型的题,,直接哭瞎了。。
需要用到无理数共轭的概念
具体题解:http://blog.csdn.net/xh_reventon/article/details/9970259
想到共轭就比较好做了。

#include<stdio.h>
#include<string.h>
typedef long long ll;
typedef struct Mat{
    ll m[3][3];
    int r,c;
    Mat(int _n,int _m)
    {
        r=_n;c=_m;
    }
    Mat(const Mat &x)
    {
        for(int i=1;i<=x.r;i++)
            for(int j=1;j<=x.c;j++)
                m[i][j]=x.m[i][j];
        r=x.r;c=x.c;
    }
}Mat;
Mat per(2,2);
ll mod;
void init(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            per.m[i][j]=(i==j);
    return;
}
Mat operator *(const Mat &a,const Mat &b)
{
    int i,j,k;
    Mat ans(a.r,b.c);
    for(i=1;i<=a.r;i++)
        for(j=1;j<=b.c;j++)
        {
            ll tmp=0;
            for(k=1;k<=b.r;k++)
                tmp=(tmp+a.m[i][k]*b.m[k][j]%mod+mod)%mod;
            ans.m[i][j]=tmp;
        }
    return ans;
}
Mat operator ^(const Mat &a,const int &kk)
{
    Mat ans=per,p=a;
    int k=kk;
    while(k)
    {
        if(k&1)
        {
            k--;
            ans=ans*p;
        }
        else
        {
            k/=2;
            p=p*p;
        }
    }
    return ans;
}
int main()
{
    int i,j;
    ll a,b,m;
    int n;
    init(2,2);
    while(~scanf("%I64d%I64d%d%I64d",&a,&b,&n,&m))
    {
        mod=m;
        a=a%mod;b=b%mod;
        Mat tmp(2,2),sr(1,2);
        tmp.m[1][1]=0;tmp.m[1][2]=(b-a*a%mod+mod)%mod;
        tmp.m[2][1]=1;tmp.m[2][2]=2*a%mod;
        sr.m[1][1]=2;sr.m[1][2]=2*a%mod;
        printf("%I64d\n",(sr*(tmp^n)).m[1][1]);


    }
    return 0;
}

欧拉回路充分性的证明&&相关要点

首先指出一点:欧拉回路的叫法是错误的,准确来说是欧拉闭迹。迹和路在离散数学中定义很明确。

握手定理:设无向图G<V,E>有m条边,则sum(degree(vi))=2*m。

引理:在一个图中,奇度点数必为偶数

证明:任意个偶数相加仍为偶数,2*m是偶数,偶数减偶数是偶数,所以sum(degree(奇度点))为偶数,又因为偶数个奇数相加为偶数,奇数个奇数相加为奇数,所以奇度点的个数为偶数。

下面给出一个链接,对欧拉回路存在定理充分性的证明,比较直观好理解:

点这里

由于欧拉回路充分性的证明是构造性的,所以这个证明其实提供了寻找欧拉回路的方法。
————————————————————————————————————————————————————————————————————
下图截自风神博客http://blog.csdn.net/shahdza/article/details/6630108

2013 ACM/ICPC Asia Regional Hangzhou Online–1008

hdoj4745 Two Rabbits
想到了就是水dp。。。

#include<stdio.h>
#include<string.h>
int a[2010],dp[2010][2010];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    int n;
    while(scanf("%d",&n) && n)
    {
        for(i=1;i<=n;i++) {scanf("%d",&a[i]);a[i+n]=a[i];}
        for(i=1;i<=2*n;i++) dp[i][i]=1;
        for(i=1;i<=2*n-1;i++) dp[i][i+1]=(a[i]==a[i+1]?2:1);
        for(int len=3;len<=n;len++)
        {
            for(i=1;i+len-1<=2*n;i++)
            {
                j=i+len-1;
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                if(a[i]==a[j]) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
            }
        }
        int ans=-1;
        for(i=1;i<=n;i++) ans=max(ans,dp[i][i+n-1]);
        for(i=1;i<=n;i++) ans=max(ans,dp[i][i+n-2]+1);
        printf("%d\n",ans);
    }
    return 0;
}

一般图的最大团

//自己第一次写的模板没用dp,怎么搞都一直2s多。。用下面的模板则可以达到700ms左右。orz。。自己加了些注释,其实很好理解
n:标号1~n,n个点
map[][]:图的邻接阵
dp[i]:表示G({i……n},ei)这个子图的最大团点数。
x[]:当前最大团
path[]:最后的最大团方案
adj[i]:与i邻接且标号比i大的顶点。
ans:算法进行到当前时刻已知的最大团点数。
注意:求出的是字典序最小的最大团。(要使字典序最大,则当=的时候不剪枝)
为什么倒着枚举:求解dp[i]的时候dp[i+1……n]都已求出
附加:算法过程中依次求出了G({n},e1)、G({n-1,n},e2)、G({n-3……n},e3)………                      G({1……n},en)这些子图的最大团。
延伸:如果要在算法过程中依次求出G({n},e1)、G({n-1,n},e2)、G({n-3……n},e3)                    ……G({1……n},en)这些子图的最大团,
那么只要:
(1)从小到大枚举每个点
(2)adj表示与i邻接且标号<i的点集(从大到小排)
(3)dp[i]表示G({1……i},ei)这个子图的最大团点数

#include<stdio.h>
#include<string.h>
const int maxn=55;
typedef struct Clique
{
	int map[maxn][maxn],dp[maxn],ans,n;
	int x[maxn],path[maxn]; // Answer output
	void init(int _n)
	{
		n=_n,ans=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
	}
	bool dfs(int *adj,int tot,int cnt)
	{
		int temp[maxn],k;
		if(!tot)
		{
			if(cnt>ans)
			{
				ans=cnt;
				for(int i=1;i<=cnt;i++) // Answer output
					path[i]=x[i];
				return true;
			}
			return false;
		}
		for(int i=1;k=0,i<=tot;i++)
		{
			if(cnt+tot-i+1<ans)
				return false;
			if(cnt+dp[adj[i]]<ans)
				return false;
			x[cnt+1]=adj[i]; // Answer output
			for(int j=i+1;j<=tot;j++)
				if(map[adj[i]][adj[j]])//adj表示与vex邻接的点,只需枚举adj[i+1……tot],因为接下来加入的点必须和vex相邻
					temp[++k]=adj[j];
			if(dfs(temp,k,cnt+1))
				return true;
		}
		return false;
	}
	int clique()
	{
		int adj[maxn],k;
		for(int i=n;k=0,i>=1;i--)
		{
			x[1]=i; // Answer output
			for(int j=i+1;j<=n;j++)
				if(map[i][j])
					adj[++k]=j;
			dfs(adj,k,1);
			dp[i]=ans;
		}
		return ans;
	}
}Clique;
Clique xh;
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n) && n)
    {
        xh.init(n);
        int res=xh.clique();
        printf("%d\n",res);
    }
    return 0;
}

2013 ACM/ICPC Asia Regional Hangzhou Online–1001

hdoj4738 Caocao’s Bridges
注意点:如果原图不连通,那么输出0,如果原图中权最小的桥的权是0,那么要输出1.

#include <stdio.h>
#include <string.h>
#define inf 0x3f3f3f3f
const int maxn=1000+10;
const int maxe=4000000+10;
typedef struct EdgeA{
    int w;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dfn[maxn],low[maxn],belong[maxn];
int id,dcc,top,n,m;
int s[maxn];
Edge bridge[maxe];  //桥边的集合,
int cnt,bcnt;       //从0开始
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void dfs(int cur,int fa)
{
    dfn[cur]=low[cur]=++id;
    s[++top]=cur;
    bool flag=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa && flag) {flag=0;continue;}//处理反向边
        if(!dfn[v])
        {
            dfs(v,cur);
            if(low[cur]>low[v])
                low[cur]=low[v];
            else if(low[v]>dfn[cur])
            {
                bridge[bcnt].w=edge[i].w;
                bridge[bcnt].from=cur;   //存的桥是原图中的标号
                bridge[bcnt].to=v;
                bcnt++;
                dcc++;
                while(s[top]!=v)
                {
                    belong[s[top]]=dcc;
                    top--;
                }
                belong[s[top]]=dcc;top--;
            }
        }
        else if(low[cur]>dfn[v])
            low[cur]=dfn[v];
    }
    return;
}
void tarjan()
{
    id=top=dcc=bcnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            dfs(i,-1);
            dcc++;
            while(top!=0)
            {
                belong[s[top]]=dcc;
                top--;
            }
        }
    }
    return;
}
bool visit[maxn];
void dfs2(int cur)
{
    visit[cur]=1;
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs2(v);
    }
    return;
}
bool connect()
{
    memset(visit,0,sizeof(visit));
    dfs2(1);
    for(int i=1;i<=n;i++)
        if(!visit[i]) {return 0;}
    return 1;
}
int main()
{
    int i,j;
    int u,v,w;
    while(scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        int mind=inf;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
            if(w<mind) mind=w;
        }
        tarjan();
        if(!connect()) {printf("0\n");continue;}
        if(dcc==1) printf("-1\n");
        else
        {
            int ans=inf;
            for(i=0;i<=bcnt-1;i++)
                if(bridge[i].w<ans) ans=bridge[i].w;
            if(ans==0) printf("1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

2013 ACM/ICPC Asia Regional Hangzhou Online–1004

hdoj4741 Save Labman No.004

#include<stdio.h>
#include<string.h>
#include<math.h>
typedef struct Point{
    double x,y,z;
}Point;
Point operator +(const Point &a,const Point &b)
{
    Point res;
    res.x=a.x+b.x;res.y=a.y+b.y;res.z=a.z+b.z;
    return res;
}
Point operator *(const Point &a,const double t)
{
    Point res;
    res.x=a.x*t;res.y=a.y*t;res.z=a.z*t;
    return res;
}
Point operator -(const Point &a,const Point &b)
{
    Point res;
    res.x=a.x-b.x;res.y=a.y-b.y;res.z=a.z-b.z;
    return res;
}
double operator *(const Point &a,const Point &b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
Point operator /(const Point &a,const Point &b)
{
    Point res;
    res.x=a.y*b.z-b.y*a.z;
    res.y=b.x*a.z-a.x*b.z;
    res.z=a.x*b.y-a.y*b.x;
    return res;
}
double daxiao(Point a)
{
    return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
}
Point p1,p2,p3,p4;
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z,&p3.x,&p3.y,&p3.z,&p4.x,&p4.y,&p4.z);
        Point n1=p2-p1;
        Point n2=p4-p3;
        Point p=n1/n2;
        Point q=p3-p2;
        double d=fabs((p*q)/daxiao(p));
        double tmp=daxiao(n1/n2);
        Point delta=p3-p1;
        double t1=((delta/n2)*(n1/n2))/(tmp*tmp);
        double t2=((delta/n1)*(n1/n2))/(tmp*tmp);
        Point ans1=p1+(n1*t1);
        Point ans2=p3+(n2*t2);
        printf("%.6f\n",d);
        printf("%.6f %.6f %.6f %.6f %.6f %.6f\n",ans1.x,ans1.y,ans1.z,ans2.x,ans2.y,ans2.z);
    }
    return 0;
}

2013 ACM/ICPC Asia Regional Chengdu Online–1010

hdoj4737 A Bit Fun
题意:给出n,m,然后给你n个正整数(n<=10^5),设f(i,j)=ai|ai+1|ai+2|……|aj,(i<=j),问有多少不同的f(i,j)<m.
总体思路:假如有一段连续的数[ai……aj aj+1],由于位或运算会使得结果越来越大,所以f(i,j)<f(i,j+1),那么可以很快得到二分的算法:一次枚举第i个数,二分[i,n]这一段数,找到最大的t,满足f(i,t)<m.
但是问题是n是10^5,每次暴力计算f(i,j)都是O(n)的(这样做就没有二分),这样复杂度是O(n^2)的,怎么降低复杂度呢(貌似这题数据比较水,比赛的时候很多大一队员是用暴力水过的,,==!)。
关键在于要常数时间计算ai|ai+1|ai+2|……|aj。可以这样做,a[i][k]表示前i个数对应第k位(把数分解成二进制)上“1”的个数之和,显然如果a[i-1][k]<a[j][k],那么说明[ai,aj]这段连续的数中至少存在一个数它的第k位是“1”,那么这段数位或起来,结果的二进制第k位一定是“1”,反之亦然。这样枚举结果的每一位分别是1还是0即可,一个数最多30位,自然是常数。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int a[100000+10][32];
int n,k;
ll bsearch(int x)
{
    int i,m;
    int l=x,r=n;
    while(l<=r)
    {
        m=(l+r)/2;
        int tmp=0;
        for(i=31;i>=0;i--)
        {
            tmp=(tmp<<1)+(a[x-1][i]!=a[m][i]);
        }
        if(tmp<k) l=m+1;
        else r=m-1;
    }
    return (ll)(r-x+1);
}
int main()
{
    int i,j,cases=0;
    int tmp;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<=31;i++) a[0][i]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&tmp);
            for(j=0;j<=31;j++)
            {
                a[i][j]=a[i-1][j]+(tmp&1);
                tmp>>=1;
            }
        }
        ll ans=0;
        for(i=1;i<=n;i++)
            ans+=bsearch(i);
        printf("Case #%d: %I64d\n",++cases,ans);


    }

    return 0;
}

稳定婚姻问题

设男生有n个,女生有m个。
(1)n=m,一定有解
(2)n!=m,少的那一方能完全匹配
(3)男生求婚,则最终答案是保证每个男生追到尽量好的女生,反之亦然
(4)求婚一方在算法进行过程中对象质量会越来越差,被动一方则相反
(5)求婚一方在订婚后可能变成单身(失配),但是被动一方一旦被求过婚,它就一定不可能单身了。

http://www.sdc1992.com/stable-marriage-problem/

Gale-Shapley算法(求婚-拒绝算法)

void gs()
{
    while(有单身男)
    {
        for(每个单身男) 按他喜欢的女生列表向没拒绝过他的女生表白
        for(每个女生) if(有表白者) 选出她喜欢列表中最靠前的那个作为男友
    }
    return;
}

关于二分图一些概念的记录

最大匹配其实就是最大边独立集
最小点覆盖集=最大边独立集
最小边覆盖集=最大点独立集
求最小点覆盖集的一个可行解:
法一:见matrix67对二分图最大匹配的König定理的证明
法二:
算法实现步骤:
1. 做最大匹配,没有匹配的空闲点∈S
2. 如果u∈S那么u的邻点必然属于T
3. 如果一对匹配的点中有一个属于T那么另外一个属于S
4. 还不能确定的,把左子图的放入S,右子图放入T
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点

关于DAG的最小路径覆盖的一些理解:
最近记忆力很差,很多结论做题的时候记得,果断时间又忘了,还是记录下来..
1.可以这样理解最小路径覆盖:开始的时候n个点,每个点需要一条路径去覆盖,然后一条匹配边会把两个路径连在一起,所以每增加一条匹配边,路径数就减少1,当达到最大匹配时,路径数最少。所以最小路径覆盖=原图总点数-最大匹配
2.也可以这样理解最小路径覆盖:二分图的最大匹配的那些弧和最小路径覆盖的弧是对应的。假如有弧,则连弧,所以对于二分匹配完的图中,u点的匹配点是n+v,意思就是v点有入边。在一条路径中,只有起始点是没有入边的,所以最少有几条路径本质就是最少有几个这样没有入边的点。那么二分匹配边的右侧点都是有入边的,剩下(原图总点数-二分匹配数)个点是没有入边的,这些点就是每条路径的起始点。
由上面的2可以得到求最小路径覆盖的可行解(最小路径覆盖可能有多个解,因为最大匹配可能有多个解)。

有向无环图最小可相交路径覆盖
定义:用最小的可相交路径覆盖所有顶点。
算法:先用floyd求出原图的传递闭包,即如果a到b有路,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

近期比赛待做的题

2013 ACM/ICPC Asia Regional Online —— Warmup
hdoj4714 Tree2cycle
hdoj4712 Hamming Distance
HDU Single Congtest 0905 (For Old ACMer)
zoj1301 The New Villa
HDU Single Congtest 0907 (For Old ACMer)
zoj1063 Space Station Shielding
zoj1066 Square Ice
zoj1197 Sorting Slides
HDU Team Congtest 0910 (For Old ACMer)
zoj1462 Team Them Up!
zoj1391 Horizontally Visible Segments