hdu 3416 最短路+最大流

2010年9月06日 04:04

求源点到终点的不共享边的最短路有多少条.

先求一次单源最短路,得到距离数组d,考虑某条边,它的起点是k1,终点是k2,边的权是c,如果d[k2]-d[k1]=c就说明这条边是最短路上的---wr大牛

原来我的想法是求一次单源最短路得到最短路长度,然后再一次求一次单源最短路并回溯来构造流网络,实在是太菜了而且流网络方面也没有想清楚......

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct Edge{int w,wt,next;}e[1000000];
int start[maxn];
int d[maxn];//单源距离

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++)
        d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int flow[maxn][maxn],maxflow[maxn],father[maxn];
int Maxflow,visit[maxn];

void ford_fulkerson(int s,int t)
{
    queue<int>Q;
    int i,u,v;
    while(1)
    {
        //memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0
        //memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列
        for(i=0;i<n;i++) maxflow[i]=visit[i]=0;
        maxflow[s]=inf;//源点的容量置为正无穷
        Q.push(s);// 将源点压入队列
        while(!Q.empty())
        {
            u=Q.front();
            Q.pop();
            for(v=0;v<n;v++) if(!visit[v]&&flow[u][v]>0)
            {
                visit[v]=1;
                father[v]=u;//记录下他的父亲方便往后的正反向更新
                Q.push(v);
                maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者
            }
            if(maxflow[t]>0)//如果找到了汇点并且汇点容量不为0则清空队列
            {
                while(!Q.empty())
                    Q.pop();
                break;
            }
        }
        if(maxflow[t]==0)//已经找不到到汇点的增广路经了,就退出整个循环
            break;
        for(i=t;i!=s;i=father[i])
        {
            flow[father[i]][i]-=maxflow[t];//正向更新
            flow[i][father[i]]+=maxflow[t];//反向更新
        }
        Maxflow+=maxflow[t];//更新最大流
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif

    int i,v,w,wt,s,t,cnt;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        cnt=0; for(v=0;v<n;v++) start[v]=-1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&v,&w,&wt);
            v--;w--;
            e[cnt].w=w;e[cnt].wt=wt;
            e[cnt].next=start[v];start[v]=cnt++;
        }
        scanf("%d%d",&s,&t);
        s--;t--;
        spfa(s);

        //for(v=0;v<n;v++)
                //cout<<v<<":"<<d[v]<<" ";
        //cout<<endl;

        Maxflow=0;
        for(v=0;v<n;v++) for(w=0;w<n;w++) flow[v][w]=0;
        for(v=0;v<n;v++)
            for(i=start[v];i!=-1;i=e[i].next)
            {
                w=e[i].w;
                if(d[w]-d[v]==e[i].wt)
                    flow[v][w]+=1;
            }
        ford_fulkerson(s,t);
        printf("%d\n",Maxflow);
    }
}

评论(1) 阅读(2454)

poj 2186 强连通分支

2010年9月05日 01:34

tarjan 485MS

原理: 在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。
定义dfn(u)为节点u的时间戳,low(u)为节点u或u的子树能追溯到的最小的栈中节点的dfn值。当dfs回溯时发现dfn(u)==low(u),则u是分量子树的根,从u到栈顶为一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef vector<int>::iterator it;
#define maxn 10001
int inline min(int a,int b){return a<b?a:b;}
vector<int> g[maxn];
int dfn[maxn],low[maxn],stack[maxn];
int idx,top;
bool instack[maxn];
int sc,f[maxn],cnt[maxn];

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    stack[top++]=u; instack[u]=1;
    for(it v=g[u].begin();v!=g[u].end();++v)
        if(!dfn[*v])//not visited
            tarjan(*v),low[u]=min(low[u],low[*v]);
        else if(instack[*v])
            low[u]=min(low[u],dfn[*v]);
    if(dfn[u]==low[u])//find root
    {
        ++sc;cnt[sc]=0;
        do { f[stack[--top]]=sc; cnt[sc]++;
            instack[stack[top]]=0; 
        } while(u!=stack[top]);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    idx=top=sc=0;
    memset(dfn,0,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    //for(int i=1;i<=n;i++) printf("%d ",f[i]);

    //缩点
    int out[sc+1];memset(out,0,sizeof(out));
    for(u=1;u<=n;u++)
        for(it v=g[u].begin();v!=g[u].end();++v)
            if(f[u]!=f[*v]) out[f[u]]++;
    int count=0,ans;
    for(int i=1;i<=sc && count<2;i++)
        if(out[i]==0) count++,ans=i;
    if(count==1) printf("%d\n",cnt[ans]);
    else puts("0");
}

kosaraju 360MS

步骤:
1. dfs原图得到拓扑序。
2. 按照拓扑序dfs反图,每个dfs树中的顶点都是一个连通分支里的。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn],gr[maxn];
int t,gs[maxn];//toposort of g
int fs,f[maxn];//result of SCC
bool vit[maxn];

void dfs(int v)
{
    vit[v]=true;
    for(it w=g[v].begin();w!=g[v].end();++w)
        if(!vit[*w]) dfs(*w);
    gs[t--]=v;//记录拓扑顺序(finish时间的反序)
}

void rdfs(int v)
{
    vit[v]=true; f[v]=fs;
    for(it w=gr[v].begin();w!=gr[v].end();++w)
        if(!vit[*w]) rdfs(*w);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        g[i].clear(), gr[i].clear();
    while(m--)
    {
        scanf("%d%d",&v,&w);
        g[v].push_back(w);
        gr[w].push_back(v);
    }
    //正向
    memset(vit,false,sizeof(vit));
    t=n;
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
    //拓扑序
    //for(int i=1;i<=n;i++)
        //printf("%d ",gs[i]);
    //puts("");
    //逆向
    memset(vit,false,sizeof(vit));
    fs=0;
    for(int i=1;i<=n;i++)//拓扑序遍历反图
        if(!vit[gs[i]]) ++fs, rdfs(gs[i]);
    //输出每个点所属的强联通号 1~fs
    //for(int i=1;i<=n;i++)
        //printf("%d ",f[i]);

    //for poj 2186 缩点
    int out[fs+1],num[fs+1];
    memset(out,0,sizeof(out));
    memset(num,0,sizeof(num));
    for(int v=1;v<=n;v++)
    {
        num[f[v]]++;
        for(it w=g[v].begin();w!=g[v].end();++w)
            if(f[v]!=f[*w]) out[f[v]]++;
    }
    int cnt=0,ans;
    for(int i=1;i<=fs && cnt<2;i++)
        if(out[i]==0) cnt++,ans=i;
    if(cnt==1) printf("%d\n",num[ans]);
    else puts("0");
}

gabow 532MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#define maxn 10001
using namespace std;
int n,m;
vector<int> g[maxn];
int pre[maxn],path[maxn],sc[maxn],s[maxn],ct[maxn];
int cnt0,cnt1,p,top;
bool outis0[maxn];

void scDfs(int w)
{
    int v,i;
    pre[w]=cnt0++;
    s[top++]=w;path[p++]=w;
    for(i=0;i<g[w].size();i++)
    {
        v=g[w][i];
        if(pre[v]==-1) scDfs(v);
        else if(sc[v]==-1)
            while(pre[path[p-1]]>pre[v]) p--;
    }
    if(path[p-1]!=w) return; else p--;
    do sc[s[--top]]=cnt1; while(s[top]!=w);
    cnt1++;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int v,w,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) g[i].clear();
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&v,&w);
        g[v-1].push_back(w-1);
    }

    p=cnt0=cnt1=top=0;
    for(int i=0;i<n;i++)
        sc[i]=pre[i]=-1;

    for(int i=0;i<n;i++)
        if(sc[i]==-1) scDfs(i);

    //缩点
    for(i=0;i<cnt1;i++) {outis0[i]=1;ct[i]=0;}
    for(i=0;i<n;i++)
    {
        ct[sc[i]]++;
        for(j=0;j<g[i].size();j++)
            if(sc[i]!=sc[g[i][j]]) outis0[sc[i]]=0;
    }
    int index,count=0;
    for(i=0;i<cnt1;i++)
        if(outis0[i]) {index=i;count++;}
    if(count==1) printf("%d\n",ct[index]);
    else printf("0\n");
    return 0;
}

 

评论(0) 阅读(1913)

poj 2135 最小费用最大流

2010年9月03日 00:00

应该可以当模板用了

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 1005
#define inf 0x3f3f3f3f
struct edge{int v,w,f,c,next;} e[50000];
int vit[maxn],dis[maxn],start[maxn],p[maxn];
int tot,n,m;
void _add(int v,int w,int f,int c)
{
    e[tot].v=v; e[tot].w=w; e[tot].f=f; e[tot].c=c;
    e[tot].next=start[v];start[v]=tot++;
}
void add(int v,int w,int f,int c)
{
    _add(v,w,f,c);
    _add(w,v,0,-c);
}
bool spfa(int s,int t,int n)//寻找费用最小的可增广路
{
    int v,w;
    queue<int> q;
    for(int i=0;i<n;i++)
    { p[i]=-1;vit[i]=0;dis[i]=inf; }
    vit[s]=1;dis[s]=0;q.push(s);
    while(!q.empty())
    {
        v=q.front();q.pop();vit[v]=0;
        for(int i=start[v];i!=-1;i=e[i].next)
            if(e[i].f)
            {
                w=e[i].w;
                if(dis[w]>dis[v]+e[i].c)
                {
                    dis[w]=dis[v]+e[i].c;
                    p[w]=i;
                    if(!vit[w]) {vit[w]=1;q.push(w);}
                }
            }
    }
    return dis[t]!=inf;
}
int cost(int s,int t,int n)
{
    int ans=0,flow=inf,i;
    while(spfa(s,t,n))
    {
        ans+=dis[t];
        for(i=p[t];i!=-1;i=p[e[i].v])//可改进量
            if(e[i].f<flow) flow=e[i].f;
        for(i=p[t];i!=-1;i=p[e[i].v])//调整
        {
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,v,w,c;
    scanf("%d%d",&n,&m);
    for(i=0;i<n+2;i++) start[i]=-1;tot=0;//初始化
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&v,&w,&c);
        add(v,w,1,c);//添加边 此题为双向边
        add(w,v,1,c);
    }
    add(0,1,2,0);add(n,n+1,2,0);//此题添加的虚拟源点汇点
    printf("%d\n",cost(0,n+1,n+2));//最小费用
    return 0;
}

评论(0) 阅读(3243)

hdu 1569 方格取数

2010年9月01日 23:09

给你一个m*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取数所在的2个格子不能相邻,并且取出的数的和最大。

最大点权独立集,应用最小割求解

构图:

增加源点s和汇点t.每个格子作为一个点,进行黑白染色(相邻的一黑一白).

源点到所有黑点引一条权为黑点点权的边.所有白点到汇点引一条权为白点点权的边.

每个黑点到与其相邻的白点引一条权为无穷的边.

结果:所有点权之和减去最小割容量(即最大流流量).

分析:

因为最大流不是无穷的,所以最小割中不会包含(黑点到白点的)无穷边.所以任意不包含无穷边的割都是一种选择方案.为什么必须是割呢?因为若割中的每一条边对应这一个不选取的点,则去掉这些点之后,原图中便不存在s--u--v--t的路的,即选择的点中没有相邻的u和v了.自然当割为最小割时,剩下的点的权和最大,为所求结果.

大概就是这样子了吧,不知道有没有理解错......

评论(0) 阅读(2280)

poj 1325 最小点覆盖

2010年8月29日 18:48

描述:有A,B俩机器,各有0~n-1和0~m-1种模式.有k个任务,既可在A的某种模式下运行又可在B的某种模式下进行,求最小的模式转换次数(A,B初始为模式0).

牛人:

每个任务化为一条线,它连接着a[i]和b[j],问题转化为求(a[]和b[]中)最少的点,
使得每条线都至少有一个端点被选(这个任务就完成了)。这个就是最小点覆盖的模型了

所以是:

            scanf("%d%d%d",&j,&x,&y);
            if(x*y!=0)
                map[x][y]=1;
 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,m;
bool map[105][105];
int match[105];
bool v[105];
bool dfs(int p)
{
    int i;
    for (i = 1; i <= m; i++)
    {
        if (map[p][i] && !v[i])
        {
            v[i] = 1;
            if (match[i] == -1 || dfs(match[i]))
            {
                match[i] = p;
                return 1;
            }
        }
    }
    return 0;
}
int Hungry()
{
    int i;
    int ans = 0;
    memset(match,-1,sizeof(match));
    for (i = 1; i <= n; i++)
    {
        memset(v, false, sizeof(v));
        if (dfs(i))
            ans++;
    }
    return ans;
}
int main()
{
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    int i,k,j,x,y;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF && n!=0)
    {
        memset(map,false,sizeof(map));
        for (i = 1; i <= k; i++)
        {
            scanf("%d%d%d",&j,&x,&y);
            if(x*y!=0)
                map[x][y]=1;
        }
        printf("%d\n",Hungry());
    }
}

评论(0) 阅读(1968)