hdoj4628——2013多校第三场Pieces

题意:给定一个长度不超16的字符串,每次可以去掉一个回文序列(序列亦即可以不连续,但要顺序不变),问最少几次可以使原字符串为空?
思路:状压dp,(比赛时队友用bfs也过了,貌似速度比状压还要快。。)dp[i]表示到达i状态所需的最小步数。
先预处理出所有状态是否是回文序列。然后dp更新的时候有两种方法:一种是访问到i,用比它大的状态更新它,即填表,一种是访问到i,则更新所有它的子状态,即刷表。但是无论哪种,在更新时都要用到一个奇技淫巧:假如j是i的子状态(i为0的位,j必为0),那么i&(j-1)就表示比j小一点的i的子状态。因为i&sth保证了是i的子状态,(j-1)&sth保证了这个状态比j小一点。这个技巧减少了许多无用状态。效率大幅提高。
复杂度分析:对于每个状态,都要枚举他的子状态:c(n,n)*2^n+c(n,n-1)*2^(n-1)+……+c(n,1)*2^1+c(n,0)*2^0=(2+1)^n=3^n
代码:
填表

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int dp[1<<16],n;
char s[20];
inline int min(int a,int b){return a<b?a:b;}
bool is(char s[])
{
    int i;
    char ss[20];
    int len=strlen(s);
    int cnt=0;
    for(i=len-1;i>=0;i--)
        ss[cnt++]=s[i];
    for(i=0;i<=len-1;i++)
        if(s[i]!=ss[i])
            break;
    if(i<=len-1)
        return 0;
    return 1;
}
bool ok[1<<16];
int main()
{
    int t;
    int i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        n=strlen(s);
        memset(dp,inf,sizeof(dp));
        memset(ok,0,sizeof(ok));
        for(i=0;i<=(1<<n)-1;i++)
        {
            char ss[20];
            int cnt=0;
            for(j=0;(1<<j)<=i;j++)
                if(i&(1<<j))
                    ss[cnt++]=s[j];
            ss[cnt++]='\0';
            if(is(ss)) ok[i]=1;
        }
        dp[(1<<n)-1]=0;
        for(i=(1<<n)-2;i>=0;i--)
        {
            int tt=((1<<n)-1)^i;
            for(j=tt;j;j=tt&(j-1))
            {
                if(!ok[j]) continue;
                dp[i]=min(dp[i],dp[i|j]+1);


            }
        }
        printf("%d\n",dp[0]);
    }


    return 0;
}

刷表

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int dp[1<<16],n;
char s[20];
inline int min(int a,int b){return a<b?a:b;}
bool is(char s[])
{
    int i;
    char ss[20];
    int len=strlen(s);
    int cnt=0;
    for(i=len-1;i>=0;i--)
        ss[cnt++]=s[i];
    for(i=0;i<=len-1;i++)
        if(s[i]!=ss[i])
            break;
    if(i<=len-1)
        return 0;
    return 1;
}
bool ok[1<<16];
int main()
{
    int t;
    int i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        n=strlen(s);
        memset(dp,inf,sizeof(dp));
        memset(ok,0,sizeof(ok));
        for(i=0;i<=(1<<n)-1;i++)
        {
            char ss[20];
            int cnt=0;
            for(j=0;(1<<j)<=i;j++)
                if(i&(1<<j))
                    ss[cnt++]=s[j];
            ss[cnt++]='\0';
            if(is(ss)) ok[i]=1;
        }
        dp[(1<<n)-1]=0;
        for(i=(1<<n)-1;i>=0;i--)
        {
            for(j=i;j;j=i&(j-1))
            {
                if(!ok[j]) continue;
                dp[i^j]=min(dp[i^j],dp[i]+1);

            }
        }
        printf("%d\n",dp[0]);
    }


    return 0;
}

强连通专题

按着风神大大的博客切啊切~
提示在每道题后面,选中即可显示
HDOJ
hdoj1269 迷宫城堡 判断是否是一个强连通★
hdoj2767Proving Equivalences 至少加几条边让整个图变成强连通★
hdoj3836 Equivalent Sets 至少加几条边让整个图变成强连通★
hdoj1827 Summer Holiday 传递的最小费用★★
hdoj3072 Intelligence System 传递的最小费用★★
hdoj3861The King’s Problem 强连通+二分匹配★★

这题必须好好记下,题意木有读懂,orz。。
题意:在有向图G中,相互可达的两个点必须划分在一个区,并且一个区里的任意两个点,至少存在一条单向路径(不经过其他区的点)。问原图最少需要划分成几个区。
思路:首先相互可达的点必须在一个区,那么强连通缩点,这样形成了一个DAG森林。问题转化为:给定一个DAG森林,最少用几条路径可以覆盖所有点,每个点只能属于一条路径。其实就是求DAG森林的最小路径覆盖,拆点转化成二分图,最小路径覆盖=原图顶点-最大匹配
通过这道题顺便学了最小路径覆盖,然后整理了一些覆盖集、独立集之间的关系,爽。
代码(匹配还没学,,用sap跑的。。囧~)

#include<stdio.h>
#include<string.h>
#define maxn 5000+10
#define maxe 100000+10
#define maxn2 10000+10
#define maxe2 400000+10
#define inf 0x3f3f3f3f
typedef struct Edge{
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt,n,m;
int dfn[maxn],low[maxn],stack[maxn],belong[maxn];
bool in[maxn];
int top,scc,index;
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
    return;
}
void dfs(int cur)
{
    int v;
    dfn[cur]=low[cur]=++index;
    stack[++top]=cur;in[cur]=1;
    for (int i=head[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].to;
        if (!dfn[v])
        {
            dfs(v);
            low[cur]=min(low[cur],low[v]);
        }
        else if (in[v]) low[cur]=min(low[cur],dfn[v]);
    }
    if (dfn[cur]==low[cur])
    {
        scc++;
        do
        {
            v=stack[top--];
            in[v]=0;
            belong[v]=scc;
        }
        while (v!=cur);
    }
    return;
}
void tarjan()
{
    int i;
    top=scc=index=0;//top=0表示栈空,栈元素从1开始,bcnt:对强连通分量标号
    memset(dfn,0,sizeof(dfn));
    memset(in,0,sizeof(in));
    for (i=1;i<=n;i++)
        if (!dfn[i])
            dfs(i);
    return;
}
typedef struct Edge2{
    int c;
    int to;
    int next;
}Edge2;
Edge2 edge2[maxe2];
int head2[maxn2];
int s,t,cnt2;
int d[maxn2],c[maxn2];
void add2(int u,int v,int c)
{
    edge2[cnt2].c=c;edge2[cnt2].to=v;edge2[cnt2].next=head2[u];
    head2[u]=cnt2++;
    edge2[cnt2].c=0;edge2[cnt2].to=u;edge2[cnt2].next=head2[v];
    head2[v]=cnt2++;
    return;
}
int dfs2(int cur,int flow)
{
    if(cur==t) return flow;
    int res=0;
    for(int i=head2[cur];i!=-1;i=edge2[i].next)
    {
        int v=edge2[i].to,c=edge2[i].c;
        if(c && d[cur]==d[v]+1)
        {
            int delta=dfs2(v,min(flow,c));
            edge2[i].c-=delta;edge2[i^1].c+=delta;
            flow-=delta;res+=delta;
            if(!flow) break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(c[d[cur]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs2(s,inf);
    return ans;
}
int main()
{
    int T;
    int i,j;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        tarjan();
        cnt2=0;memset(head2,-1,sizeof(head2));
        s=0;t=2*scc+1;
        for(i=0;i<=cnt-1;i++)
        {
            int u=edge[i].from,v=edge[i].to;
            if(belong[u]!=belong[v])
            {
                add2(belong[u],scc+belong[v],inf);
            }
        }
        for(i=1;i<=scc;i++)
        {
            add2(s,i,1);add2(scc+i,t,1);
        }
        n=t+1;
        printf("%d\n",scc-sap());
    }
    return 0;
}


hdoj3639Hawk-and-Chicken 强连通缩点 + 树形dp(累加子节点的总权值)★★
hdoj3594 Cactus 仙人掌图★★★
关于仙人掌图的性质及证明:http://files.cnblogs.com/ambition/cactus_solution.pdf
周东的论文:http://wenku.baidu.com/view/76e5ff1ffad6195f312ba612
关键是对dfs树的改造

#include<stdio.h>
#include<string.h>
#define maxn 20000+10
#define maxe 50000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt,n,m;
int dfn[maxn],low[maxn],s[maxn],belong[maxn];
bool in[maxn];
int top,scc,index;
bool flag;
int a[maxn],b[maxn],fa[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
    return;
}
void dfs(int cur)
{
    int v;
    dfn[cur]=low[cur]=++index;
    s[++top]=cur;in[cur]=1;
    for (int i=head[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].to;
        if (!dfn[v])
        {
            fa[v]=cur;
            dfs(v);
            low[cur]=min(low[cur],low[v]);
        }
        else if (in[v]) {low[cur]=min(low[cur],dfn[v]);b[cur]++;}
        else
        {
            flag=0;
        }
    }
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(fa[v]==cur && low[v]>dfn[cur]){flag=0;}
        else if(fa[v]==cur && low[v]<dfn[cur]) a[cur]++;
    }
    if (dfn[cur]==low[cur])
    {
        scc++;
        do
        {
            v=s[top--];
            in[v]=0;
            belong[v]=scc;
        }
        while (v!=cur);
    }
    return;
}
void tarjan()
{
    int i;
    top=scc=index=0;
    memset(dfn,0,sizeof(dfn));
    memset(in,0,sizeof(in));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for (i=1;i<=n;i++)
        if (!dfn[i])
            dfs(i);
    return;
}
int main()
{
    int i,j;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        int aa,bb;
        scanf("%d%d",&aa,&bb);
        while(!(aa==0 && bb==0))
        {
            aa++;bb++;
            add(aa,bb);
            scanf("%d%d",&aa,&bb);
        }
        flag=1;
        tarjan();
        if(scc!=1)
            printf("NO\n");
        else if(!flag) printf("NO\n");
        else
        {
            for(i=1;i<=n;i++)
                if(a[i]+b[i]>=2) break;
            if(i>n) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

POJ
poj1236Network of Schools
poj2553 The Bottom of a Graph 好题! 找出度为0的集合
poj2186 Popular Cows 好题! 找出度为0的,其他分量都指向它的集合
poj2375Cow Ski Area 强连通
poj2762 Going from u to v or from v to u? 缩点+拓扑排序
poj3160 Father Christmas flymouse 强连通+最短路
poj3180 The Cow Prom 判断有几个环, 分量中元素大于1的个数
poj3114Countries in War 强连通+最短路
poj3592Instantaneous Transference 强连通分量+最长路
poj1904King’s Quest 强连通+并查集

http://blog.csdn.net/shiqi_614/article/details/7833628

网络流之最小费用最大流

每次找费用最小的增广路即可。

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 100
#define maxe 1000000
#define inf 1000000000
using namespace std;
typedef struct Edge{
    int from,to;
    int c;
    int w;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn],pre[maxn];
bool in[maxn];
int s,t,n,m,cnt;
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int c,int w)
{
    edge[cnt].c=c;edge[cnt].w=w;
    edge[cnt].from=u;edge[cnt].to=v;
    edge[cnt].next=head[u];head[u]=cnt++;
    return;
}
int spfa(int s,int t)
{
    int i;
    queue<int> q;
    memset(in,0,sizeof(in));
    memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;
    in[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        in[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,c=edge[i].c,w=edge[i].w;
            if(c && dist[v]+w<dist[u])
            {
                dist[u]=dist[v]+w;pre[v]=i;
                if(!in[v])
                {
                    in[v]=1;q.push(v);
                }
            }
        }
    }
    if(dist[t]==inf) return 0;
    int delta=inf;
    int p=t;
    while(p!=s)
    {
        i=pre[p];
        delta=min(delta,edge[i].c);
        p=edge[i].from;


    }
    p=t;
    while(p!=s)
    {
        i=pre[p];
        edge[i].c-=delta;edge[i^1].c+=delta;
        p=edge[i].from;
    }
    return dist[t]*delta;
}
int mfmc()
{
    int ans=0;
    while(int delta=spfa(s,t)) ans+=delta;
    return ans;
}

网络流专题

把原来讲座的网络流专题补上。。
网络流题集:风神博客
不错的博客:http://yangzhang91.com/%E7%BD%91%E7%BB%9C%E6%B5%81%E4%B8%93%E8%BE%91.htm

http://wenku.baidu.com/view/46fda12b4b73f242336c5f86.html

http://wenku.baidu.com/view/0fbab168af1ffc4ffe47ac83.html

最大流
hdoj1532 Drainage Ditches
最大流入门题

#include<stdio.h>
#include<string.h>
#define maxn 200
#define maxe 400
#define inf 1000000000
int n,m;
int s,t;
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe+10];
int head[maxn+10];
bool visit[maxn+10];
int cnt;
int d[maxn+10],c[maxn+10];
int min(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++;
    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;
        int 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==0)
                break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(c[d[cur]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        cnt=0;
        s=1;t=n;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        int from,to,c;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&from,&to,&c);
            add(from,to,c);add(to,from,0);
        }
        printf("%d\n",sap());



    }
    return 0;
}

hdoj3549 Flow Problem
网络流入门题
代码略
hdoj3572 Task Schedule
关键是建模,加入超级源汇点,以每个task和每个日期为顶点,从源点出发向每个task连边,容量为pi,从每个task向它所要求的日期范围内的日期点连边,容量1,从每个日期点向汇点连边,容量m,因为每天同时最多有m台机器工作

#include<stdio.h>
#include<string.h>
#define maxn 2000
#define maxe 800000+10
#define inf 1000000000
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int d[maxn],c[maxn];
int s,t,cnt;
int n,N,m;
int min(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++;
    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;
        int 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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
int main()
{
    int i,j,T,cases=0;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&N,&m);
        int maxday=-1,sum=0;
        for(i=1;i<=N;i++)
        {
            int p,si,ei;
            scanf("%d%d%d",&p,&si,&ei);sum+=p;
            maxday=ei>maxday?ei:maxday;
            add(0,i,p);add(i,0,0);
            for(j=N+si;j<=N+ei;j++)
                add(i,j,1),add(j,i,0);
        }
        for(i=N+1;i<=N+maxday;i++)
            add(i,N+maxday+1,m),add(N+maxday+1,i,0);
        s=0;t=N+maxday+1;n=t+1;
        if(sap()==sum)
            printf("Case %d: Yes\n",++cases);
        else
            printf("Case %d: No\n",++cases);
        printf("\n");
    }
    return 0;
}

hdoj3046 Pleasant sheep and big big wolf
这题点数最多40000点,又是完全图,按道理边数是8*10^8左右,当然程序里面开不下,于是开8*10^7,居然ac了。。
相邻的点之间连边,容量为1,建超级源汇点,从源点向每个sheep点连边,容量inf,从每个wolf点向汇点连边,容量inf。
这样,问题就转化成求最小割的容量是多少了,也就是最大流。

#include<stdio.h>
#include<string.h>
#define maxn 50000
#define maxe 80000000+10
#define inf 1000000000
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m,cnt;
int s,t;
int d[maxn],c[maxn];
void add(int u,int v,int c)
{
    edge[cnt].c=c;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
inline int min(int a,int b){return a<b?a:b;}
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(c,flow));
            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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
inline int cal(int x,int y){return (x-1)*m+y;}
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m)
        return true;
    return false;
}
int map[210][210];
int main()
{
    int i,j,cases=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        s=0;t=n*m+1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&map[i][j]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                int from=cal(i,j);
                if(judge(i-1,j)) add(from,cal(i-1,j),1),add(cal(i-1,j),from,0);
                if(judge(i+1,j)) add(from,cal(i+1,j),1),add(cal(i+1,j),from,0);
                if(judge(i,j-1)) add(from,cal(i,j-1),1),add(cal(i,j-1),from,0);
                if(judge(i,j+1)) add(from,cal(i,j+1),1),add(cal(i,j+1),from,0);
                if(map[i][j]==1) add(s,from,inf),add(from,s,0);
                if(map[i][j]==2) add(from,t,inf),add(t,from,0);
            }
            n=n*m+2;
            printf("Case %d:\n%d\n",++cases,sap());
    }

    return 0;
}

hdoj1565、hdoj1569方格取数,两题一样,只给出hdoj1569的代码
两题都是求无向图的最大点权独立集。
最大点权独立集=最小点权覆盖集=最小割容量=最大流
构图:原矩阵可以黑白染色,新建超级源汇点,从源点向每个黑色点连边,权为黑色点点权,从每个白色点向汇点连边,权为白色点点权。从每个黑色点向它相邻的白色点连边,容量inf。构图完毕。

#include<stdio.h>
#include<string.h>
#define maxn 2600
#define maxe 5000000
#define inf 1000000000
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int s,t,cnt,n,m;
int d[maxn],c[maxn];
inline int min(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++;
    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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m)
        return true;
    return false;
}
int cal(int x,int y)
{
    return (x-1)*m+y;
}
int main()
{
    int i,j;
    int map[55][55];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        s=0;t=n*m+1;
        int sum=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                sum+=map[i][j];
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i+j)&1)
                {
                    int p=(i-1)*m+j;
                    add(p,t,map[i][j]);add(t,p,0);
                }
                else
                {
                    int p=(i-1)*m+j;
                    add(s,p,map[i][j]);add(p,s,0);
                    if(judge(i-1,j)) add(p,cal(i-1,j),inf),add(cal(i-1,j),p,0);
                    if(judge(i+1,j)) add(p,cal(i+1,j),inf),add(cal(i+1,j),p,0);
                    if(judge(i,j-1)) add(p,cal(i,j-1),inf),add(cal(i,j-1),p,0);
                    if(judge(i,j+1)) add(p,cal(i,j+1),inf),add(cal(i,j+1),p,0);
                 }
            }
            n=t+1;
            printf("%d\n",sum-sap());
    }

    return 0;
}

hdoj2732 Leapin’ Lizards
hdoj4183 Pahom on Water
hdoj4289 Control


hdoj4292 Food


hdoj2883 kebab
hdoj4240 Route Redundancy
hdoj3081 Marriage Match II
hdoj3277 Marriage Match III
hdoj3416 Marriage Match IV
hdoj4309 Seikimatsu Occult Tonneru
费用流
hdoj1533 Going Home


hdoj2686 Matrix


hdoj3376 Matrix Again


hdoj3435 A new Graph Game
hdoj1853 Cyclic Tour
hdoj3667 Transportation
hdoj3395 Special Fish
hdoj2448 Mining Station on the Sea
这题必须说一下,通过这题,最大的收获是原来的费用流模板是有漏洞的,mfmc以spfa返回0作为结束,这样,当某次增广路费用是0的时候,虽然接下来仍然可能找到增广路。但是由于返回的delta*dist[t]是0,所以mfmc直接结束了。这样就造成了错误。

#include<stdio.h>
#include<string.h>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 1000+10
#define maxe 400000+10
using namespace std;
typedef struct Edge{
    int from,to,c,w,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,n,m,k,p,cnt;
int dist[maxn],pre[maxn];
bool in[maxn];
int maxflow;
int min(int a,int b)
{
    return a<b?a:b;
}
void add(int u,int v,int c,int w)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].c=c;edge[cnt].w=w;
    edge[cnt].next=head[u];head[u]=cnt++;
    edge[cnt].from=v;edge[cnt].to=u;edge[cnt].c=0;edge[cnt].w=-w;
    edge[cnt].next=head[v];head[v]=cnt++;
    return;
}
int spfa()
{
    int i;
    queue<int> q;
    memset(in,0,sizeof(in));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<=t;i++) dist[i]=inf;
    in[s]=1;
    dist[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        in[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,c=edge[i].c,w=edge[i].w;
            if(c && dist[u]+w<dist[v])
            {
                dist[v]=dist[u]+w;pre[v]=i;
                if(!in[v])
                {
                    in[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dist[t]>=inf)
        return 0;
    return 1;
}
int mfmc()
{
    int ans=0;
    while(spfa())
    {
        int i,p,delta=inf;
        p=t;
        while(p!=s)
        {
            i=pre[p];
            delta=min(delta,edge[i].c);
            p=edge[i].from;
        }
        p=t;
        while(p!=s)
        {
            i=pre[p];
            edge[i].c-=delta;edge[i^1].c+=delta;
            p=edge[i].from;
        }
        maxflow+=delta;
        ans+=delta*dist[t];
    }
    return ans;
}
int main()
{
    int i,j;
    while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF)
    {
        maxflow=0;
        cnt=0;
        memset(head,-1,sizeof(head));
        s=0;t=m+n+1;
        for(i=1;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(s,tmp,1,0);
        }
        for(i=1;i<=k;i++)
        {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            add(a,b,inf,w);add(b,a,inf,w);
        }
        for(i=1;i<=p;i++)
        {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            add(b,m+a,inf,w);
        }
        for(i=1;i<=n;i++)
            add(m+i,t,1,0);
        printf("%d\n",mfmc());
    }
    return 0;
}

最小割
hdoj3657 Game
这题是最大权独立集的变形。
首先来分析最小权覆盖集,因为它与最大权独立集是互补的。
最小权覆盖集:建边时,对于相邻的点:s-(val[u])-u-(inf)-v-(val[v])-t。这样就保证这条路径至少有一条边在割中,又因为是最小割,所以有且只有一条在最小割中。因为中间的边设为inf,这样这条边就不可能在最小割中,所以最小割必为简单割。所以val[u]、val[v]两条边中,有且只有一条会在最小割中,这就保证了有边相连的两个点必定会取其中的一个点,这满足最小权覆盖集的定义。假如说权为val[u]的边在最小割中,意思就是点u在最小覆盖集中。
最大独立集和最小覆盖集是互补的,所以(总权值-最小割)就是最大权独立集。
(注意:以下部分所说的最小权覆盖集合最大权独立集实质上不是它们本身的定义了)
事实上,进一步思考会发现,既然割掉与源点/汇点相连的边相当于将对应的点取入最小权覆盖集,那么如果割的是中间的边呢,显然意思是两个点都没取。为什么这么说呢,因为我们说最小割就是最小权覆盖集,那么因为取的是中间的边,所以两个点的权值(两头的边)都没有加入最小割中,自然就意味着这两个点都没选入最小权覆盖集。
再进一步,既然两个点都没取选入最小权覆盖集,那么它们必然是在最大权独立集中的,所以假如题目说“最大权独立集”可以取相邻的两个点,只是同时选时要减去x(x小于这两个点的权),那么实际上只要把相邻点之间的边权设为x即可,这样当选中这条边时,相当于两个点都在“最大权独立集”中(因为都没在“最小权覆盖集”)。所以最后总权值-最小割时就把x减去了,也就意味着两个都在“最大权独立集”中时,减去x。

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
#define maxn 3000+10
#define maxe 20000+10
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int d[maxn],c[maxn];
int s,t,n,m,k,cnt;
inline int min(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;
}
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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
int index(int x,int y)
{
    return (x-1)*m+y;
}
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m)
        return true;
    return false;
}
int map[55][55];
int main()
{
    int i,j;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        cnt=0;s=0;t=n*m+1;
        memset(head,-1,sizeof(head));
        int sum=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                sum+=map[i][j];
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i+j)&1)
                {
                    int u=index(i,j);
                    if(judge(i,j-1)) add(u,index(i,j-1),2*(map[i][j]&map[i][j-1]));
                    if(judge(i,j+1)) add(u,index(i,j+1),2*(map[i][j]&map[i][j+1]));
                    if(judge(i-1,j)) add(u,index(i-1,j),2*(map[i][j]&map[i-1][j]));
                    if(judge(i+1,j)) add(u,index(i+1,j),2*(map[i][j]&map[i+1][j]));
                }
            }
        for(i=1;i<=k;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a][b]=inf;

        }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i+j)&1)
                    add(s,index(i,j),map[i][j]);
                else
                    add(index(i,j),t,map[i][j]);
            }
        n=t+1;
        printf("%d\n",sum-sap());
   }
    return 0;
}

hdoj3061
最大权闭形图。
新建超级源点和超级汇点,从源点向所有正权点引边,边权为点权;从所有负权点向汇点连边,边权为点权绝对值。图中原来的边边权为inf。
最大权闭形图权值=图中正点权之和-最小割。
而跑完最大流后的S集合即使是最大权闭形图的点(去掉源点)。

#include<stdio.h>
#include<string.h>
#define maxn 500+10
#define maxe 260000+10
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int c[maxn],d[maxn];
int s,t,n,m,cnt;
inline int min(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;
}
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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%d",&m);
        cnt=0;s=0;t=n+1;
        int sum=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            if(tmp>0)
            {
                sum+=tmp;
                add(s,i,tmp);
            }
            else if(tmp<0)
            {
                add(i,t,-tmp);
            }
        }
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b,inf);
        }
        n=t+1;
        printf("%d\n",sum-sap());


    }
    return 0;
}

hdoj3996 Gold Mine
题意其实很清楚,看完就知道是最大权闭包。但是写起来比较烦,因为数据未读完时不知道汇点的下标(当然可以设成很大的数,但这不是我的风格)。可以把不同的layout看成不同的行,把每个layout含有的金子数看成列,先全部读入数据,再处理。每个金子的前驱用一个结构体数组来指向。

#include<stdio.h>
#include<string.h>
#define maxn 30000+10
#define maxe 8000000+10
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
typedef struct Edge{
    ll c;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int c[maxn],d[maxn];
int s,t,n,m,cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
void add(int u,int v,ll 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;
}
ll dfs(int cur,ll flow)
{
    if(cur==t) return flow;
    ll res=0;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        ll c=edge[i].c;
        if(c && d[cur]==d[v]+1)
        {
            ll delta=dfs(v,min(flow,c));
            edge[i].c-=delta;edge[i^1].c+=delta;
            flow-=(ll)delta;res+=(ll)delta;
            if(!flow) break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(c[d[cur]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
ll sap()
{
    ll ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
typedef struct Pnt{
    int x,y;
}Pnt;
typedef struct Node{
    int index;
    ll pro;
    int num;
    Pnt p[60];
}Node;
Node map[110][30];
int main()
{
    int T,cases=0;
    int i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        int row,col,tot=0;
        scanf("%d",&row);
        for(i=1;i<=row;i++)
        {
            scanf("%d",&col);
            map[i][0].pro=col;
            for(j=1;j<=col;j++)
            {
                int a,b,num;
                scanf("%lld%lld%d",&a,&b,&num);
                tot++;
                map[i][j].index=tot;
                map[i][j].pro=b-a;
                map[i][j].num=num;
                for(k=1;k<=num;k++)
                {
                    scanf("%d%d",&map[i][j].p[k].x,&map[i][j].p[k].y);
                }
            }
        }
        s=0;t=tot+1;
        ll sum=0;
        for(i=1;i<=row;i++)
        {
            for(j=1;j<=map[i][0].pro;j++)
            {
                if(map[i][j].pro>0)
                {
                    sum+=map[i][j].pro;
                    add(s,map[i][j].index,map[i][j].pro);
                }
                else if(map[i][j].pro<0)
                    add(map[i][j].index,t,-map[i][j].pro);
                for(k=1;k<=map[i][j].num;k++)
                {
                    int x=map[i][j].p[k].x,y=map[i][j].p[k].y;
                    int index=map[x][y].index;
                    add(map[i][j].index,index,inf);
                }
            }
        }
        n=t+1;
        printf("Case #%d: %I64d\n",++cases,sum-sap());

    }
    return 0;
}

hdoj3251 Being a Hero
题意:给你f个点,这些点每个点都有一个正点权(收入),国王在点1,如果选了f个点中的某些点,那么必须去掉一些边使得点1无法到达这些选中的点。去掉一条边都有对应的费用,问最后能赚多少。
思路:最小割模型:以1为源点,n+1为汇点,从所有f个可选的点向汇点连边,权为点权。其他按原图连边,求最小割。答案为总点权-最小割
想法:因为如果没有选某个点,那么这个点到汇点的连边必然会在最小割中(可反证:如果没选该点但这条边没在最小割中,那么这条边就不必要割去了,因为是最小割,那么这个点不是不选白不选吗,所以必然会去选,矛盾)。

/* 求AC~
    =    =  !!
      ''    !!
      ~~
浩哥专用,版权所有,切勿侵权
*/
#include<stdio.h>
#include<string.h>
#define maxn 1010
#define maxe 500010
#define inf 0x3f3f3f3f
typedef struct Edge{
    int id;
    int c;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,cnt,n,m;
int c[maxn],d[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int c,int id)
{
    edge[cnt].id=id;edge[cnt].c=c;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].id=id;edge[cnt].c=0;edge[cnt].from=v;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
bool can[maxn];
bool color[maxn];
void dfs2(int cur)
{
    color[cur]=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        //if(i&1) continue;
        int v=edge[i].to,c=edge[i].c;
        if(color[v] || c==0) continue;
        dfs2(v);
    }
    return;
}
int main()
{
    int T,cases=0;
    int i,j,k,f;
    int u,v,c,id;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&f);
        cnt=0;memset(head,-1,sizeof(head));
        s=1;t=n+1;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,c,i);
        }
        int sum=0;memset(can,0,sizeof(can));
        for(i=1;i<=f;i++)
        {
            scanf("%d%d",&u,&c);
            add(u,t,c,id);sum+=c;can[u]=1;
        }
        n=t;
        printf("Case %d: %d\n",++cases,sum-sap());
        int count=0;memset(color,0,sizeof(color));
        dfs2(1);
        int ans[maxn],iq=0;
        for(i=0;i<=cnt-1;i+=2)
        {
            u=edge[i].from;v=edge[i].to;
            c=edge[i].c;
            int id=edge[i].id;
            if(u==t || v==t) continue;
            if(color[u]==color[v] || c) continue;
            count++;
            ans[++iq]=id;
        }
        printf("%d",count++);
        for(i=1;i<=iq;i++)
            printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}

hdoj3313 Key Vertex
TLE中,待修改。。。。

#include<stdio.h>
#include<string.h>
#define maxn 200000+10
#define maxe 400000+10
#define inf 0x3f3f3f3f
typedef struct Edge{
    int c;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int s,t,n,m,cnt;
int d[maxn],c[maxn];
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int c)
{
    edge[cnt].c=c;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].c=0;edge[cnt].from=v;edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    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(c,flow));
            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]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0,i,j;
    for(i=1;i<=n;i++) c[i]=0;
    for(i=1;i<=n;i++) d[i]=0;
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
bool visit[maxn];
int list[maxn],iq;
void dfs2(int cur)
{
    visit[cur]=1;
    list[++iq]=cur;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to,c=edge[i].c;
        if(visit[v] || !c) continue;
        dfs2(v);
    }
    return;
}
int work()
{
    int i,j;
    for(i=1;i<=n;i++) visit[i]=0;
    int now=s,ans=0;
    while(1)
    {
        iq=0;
        dfs2(now);
        bool flag=0;
        for(i=1;i<=iq;i++)
        {
            if(flag) break;
            for(j=head[list[i]];j!=-1;j=edge[j].next)
            {
                int v=edge[j].to,c=edge[j].c;
                if(!visit[v] && !c && !(j&1))
                {
                    ans++;
                    now=v;
                    flag=1;
                    if(v==t) return ans;
                }
            }
        }
    }
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int u,v;
        cnt=0;
        for(i=1;i<=2*n;i++) head[i]=-1;
        for(i=1;i<=m;i++)
        {
            scan(u);scan(v);u++;v++;
            add(n+u,v,inf);
        }
        scanf("%d%d",&s,&t);s++;t++;
        for(i=1;i<=n;i++)
        {
            if(i!=s && i!=t) add(i,n+i,1);
            else add(i,n+i,2);
        }
        t=n+t;
        int nn=n;n=2*n;
        int ans=sap();
        if(ans==0) {printf("%d\n",nn);continue;}
        if(ans==2) {printf("2\n");continue;}
        edge[head[s]].c=0;edge[head[t-nn]].c=0;
        printf("%d\n",work());


    }

    return 0;
}

网络流之sap

用dfs形式的朴素算法实现FF思想(hdoj1532)

#include<stdio.h>
#include<string.h>
#define maxn 200
#define maxe 400
#define inf 1000000000
int n,m;
int s,t;
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe+10];
int head[maxn+10];
bool visit[maxn+10];
int cnt;
int min(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++;
    return;
}
int dfs(int cur,int flow)//flow表示从原点到现在该点为止路径上的最小容量(注意:这里的提到的网络都将是指残余网络)
{
    visit[cur]=1;
    if(cur==t) return flow;
    int res=0;//res的含义:dfs的返回值,表示从该点到汇点的所有路径能得到的增广总量
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        int c=edge[i].c;
        if(c && !visit[v])
        {
            int delta=dfs(v,min(flow,c));//delta:用来获得当前点的后继点v开始的路径所能增广的总量
            visit[v]=0;
            edge[i].c-=delta;edge[i^1].c+=delta;
            flow-=delta;res+=delta;//因为s->……->cur->v->……->t的所有路径总共增广了delta,所有s->……->cur到cur为止的最小容量要减去delta。而res是向前传递的表示经过当前点往后的路径中总共可增广量,所以要加上delta
        }
    }
    return res;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        cnt=0;
        s=1;t=n;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        int from,to,c;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&from,&to,&c);
            add(from,to,c);add(to,from,0);
        }
        printf("%d\n",dfs(s,inf));



    }
    return 0;
}

这个算法即使是这个水题也会超时,但是理解它对后面学习sap算法益处良多
一个疑惑:残余网络中的反向边是为了程序在找增广路时可以反悔,当一条边流过的太多时,可以反向流回来一些,但是具体怎么做到的,还是没有很形象很清晰的理解透彻。
sap+gap的代码

#include<stdio.h>
#include<string.h>
#define maxn 200
#define maxe 400
#define inf 1000000000
int n,m;
int s,t;
typedef struct Edge{
    int c;
    int to;
    int next;
}Edge;
Edge edge[maxe+10];
int head[maxn+10];
bool visit[maxn+10];
int cnt;
int d[maxn+10],c[maxn+10];
int min(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++;
    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;
        int 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==0)
                break;
        }
    }
    if(!res)
    {
        c[d[cur]]--;
        if(c[d[cur]]==0) d[s]=n;
        d[cur]++;
        c[d[cur]]++;
    }
    return res;
}
int sap()
{
    int ans=0;
    memset(d,0,sizeof(d));
    memset(c,0,sizeof(c));
    c[0]=n;
    while(d[s]<n) ans+=dfs(s,inf);
    return ans;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        cnt=0;
        s=1;t=n;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        int from,to,c;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&from,&to,&c);
            add(from,to,c);add(to,from,0);
        }
        printf("%d\n",sap());
    }
    return 0;
}

速度果然快,0ms过
几个要点:
1.反向边:反悔用的,一次增广下去不一定能得到最大流
2.为什么没有visit数组了
答:visit数组是为了保证增广路径是简单路径,而d[cur]==d[v]+1这个条件已经保证了不会走一个圈,即保证了走的是简单路径
3.为什么距离标号d初始化为0,而res==0的时候d[cur]++?
答:res等于0表示没找到增广路径,此时把该点d加上1,并后退到上一个点。
4.为什么d变化时,如果距离标号等于d的点个数为0,就说明出现了断层?
答:当d变化时,肯定是变大,那么如果此时标号为d的点个数为0,说明从源点最远到达标号为d+1的点了,无法到达汇点,即出现断层。有人可能会说,有可能之后某个标号为d-1的点会增大到d啊,这样标号等于d的点不就又有了吗?事实上是,如果连距离标号等于d的点都到达不了,又怎么到达得了标号等于d-1的点呢。。
5。据soal大神所说,sap只要加上两个优化就行了:
(1)当flow等于0的时候,直接break,不用往后dfs了,因为这条路显然已经断了.
(2)gap优化:当出现断层时,结束算法。

树形dp专题(更新ing)

前段时间做线段树,结果做不下去了。。感觉dp太弱,遂打算做个专题,tree dp之后是状压,往后是数位dp和概率dp,不过图论也要抓起来
几个链接:
背包九讲:http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
论文《几类背包问题》:http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html
依赖背包博文:http://www.cnblogs.com/GXZC/archive/2013/01/13/2858649.html
zero clock背包总结:http://blog.csdn.net/woshi250hua/article/details/7636866
开个树形dp专题:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25888#overview
(一)一般树形dp
(二)树形dp+分组背包
因为有分支,所以树上的背包要容量要分配,但是因为是依赖背包,所以根一定要选。从根往下看是分配,代码中实际是从叶子往上合并的,这种合并其实就是dd神牛的背包九讲里面的泛化物品,实质是把对一棵子树的决策(分配多少容量给该子树,因为决策互斥)作为一件物品,这样,合并=实际上就是做一次分组背包,一棵子树就是一个组,每组物品有dp[son][0]~dp[son][V-w[fa]]。为什么是V-w[fa]呢,因为父节点时一定要选的,所以给子节点的容量最多也就V-w[fa]。
////////////////////////////////////
hdoj1561
典型的依赖背包,因为可能是深林,所以以0为虚拟根,val[0]=0,w[0]=1;

#include<stdio.h>
#include<string.h>
#define maxn 200
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxn+10];
int head[maxn+10];
int w[maxn+10],val[maxn+10],cnt;
int fa[maxn+10];
int dp[maxn+10][210];
int n,V;
void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void dfs(int cur)
{
    int i,j,k;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        dfs(v);
        for(j=V;j>=0;j--)
        {
            for(k=0;k<=V-w[cur];k++)
            {
                if(j>=k)
                {
                    if(dp[cur][j-k]+dp[v][k]>dp[cur][j])
                        dp[cur][j]=dp[cur][j-k]+dp[v][k];
                }
            }
        }
    }
    for(j=V;j>=0;j--)
        if(j>=w[cur])
            dp[cur][j]=dp[cur][j-w[cur]]+val[cur];
        else
            dp[cur][j]=0;
    return;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&V)!=EOF && !(n==0 && V==0))
    {
        V++;
        int root;
        cnt=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            val[i]=b;w[i]=1;
            add(a,i);
        }
        val[0]=0;w[0]=1;
        memset(dp,0,sizeof(dp));
        dfs(0);
        printf("%d\n",dp[0][V]);
    }
    return 0;
}

poj1155
题意:电视台向用户播放节目,叶子结点是用户,其他结点时转发器,每条边都有一个权值,表示经过这条边转发时的花费,每个用户有一个value,表示如果让他收看节目,它会付的费。问在电视台不亏损的情况下最多让几个用户看节目?
思路:
树形分组背包。
dp[i][j]表示以结点i为根的子树让j个用户看节目的最大收入。j最大是子树i中的叶子数量,所以可以先dfs一遍求出每个子树的叶子数。
dp的转移:从下往上转移时,可以看成背包,一个子树的每个决策可以看成一件物品(一个子树选几个用户是互斥的,此时dp[某子树][j]已经正确求出),子树的数量就是组的数量。
注意dp数组的初始化:对于任意子树,选0个用户的收入肯定是0,所以dp[i][0]=0;对于叶子结点dp[i][1]=val[i];
转移:dp[i][j]=max{dp[i][j],dp[i][j-k]+dp[son][k]-w}
k是子树son的容量,也就是在子树son中选k个用户。相当于子树son中的第k+1个物品,其value是dp[son][k],w是在这个子树中选>=1个用户时的转发费用(边权)。
注意点:if(dp[cur][j-k]+dp[v][k]-ww>dp[cur][j]) 当k=0,也就是对于子树v,取容量0这件物品(即子树v里面不选任何用户)时,其实没有在子树v内选任何用户,所以没有向该子树转发,所以不用转发费,即ww=0;

#include<stdio.h>
#include<string.h>
#define maxn 3000
#define inf 1000000000
typedef struct Edge{
    int to;
    int w;
    int next;
}Edge;
Edge edge[maxn+10];
int head[maxn+10];
int n,m,cnt;
int val[maxn+10],dp[maxn+10][maxn+10];
int ye[maxn+10];
void add(int u,int v,int w)
{
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void init(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        init(v);
        ye[cur]+=ye[v];
    }
    return;
}
void dfs(int cur)
{
    int i,j,k;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        int w=edge[i].w;
        dfs(v);
        for(j=ye[cur];j>=0;j--)
        {
            for(k=0;k<=ye[v];k++)
            {
                if(j>=k)
                {
                    int ww=w;
                    if(k==0) ww=0;
                    if(dp[cur][j-k]+dp[v][k]-ww>dp[cur][j])
                    {
                        dp[cur][j]=dp[cur][j-k]+dp[v][k]-ww;

                    }
                }
            }
        }
    }
    return;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(ye,0,sizeof(ye));

        for(i=1;i<=n-m;i++)
        {
            int k;
            scanf("%d",&k);
            for(j=1;j<=k;j++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                add(i,a,b);
            }
        }
        for(i=1;i<=n;i++)
            for(j=0;j<=maxn;j++)
                if(j==0) dp[i][j]=0;
                else dp[i][j]=-inf;
        for(i=n-m+1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            dp[i][1]=val[i];
            ye[i]=1;
        }
        init(1);
        dfs(1);
        for(j=ye[1];j>=0;j--)
            if(dp[1][j]>=0)
                break;
        printf("%d\n",j);
    }
    return 0;
}

(三)