首页 > ACM题库 > HDU-杭电 > HDU 3046-Pleasant sheep and big big wolf-网络流-[解题报告]HOJ
2014
02-27

HDU 3046-Pleasant sheep and big big wolf-网络流-[解题报告]HOJ

Pleasant sheep and big big wolf

问题描述 :

In ZJNU, there is a well-known prairie. And it attracts pleasant sheep and his companions to have a holiday. Big big wolf and his families know about this, and quietly hid in the big lawn. As ZJNU ACM/ICPC team, we have an obligation to protect pleasant sheep and his companions to free from being disturbed by big big wolf. We decided to build a number of unit fence whose length is 1. Any wolf and sheep can not cross the fence. Of course, one grid can only contain an animal.
Now, we ask to place the minimum fences to let pleasant sheep and his Companions to free from being disturbed by big big wolf and his companions.
Picnic Cows

输入:

There are many cases.
For every case:

N and M(N,M<=200)
then N*M matrix:
0 is empty, and 1 is pleasant sheep and his companions, 2 is big big wolf and his companions.

输出:

There are many cases.
For every case:

N and M(N,M<=200)
then N*M matrix:
0 is empty, and 1 is pleasant sheep and his companions, 2 is big big wolf and his companions.

样例输入:

4 6
1 0 0 1 0 0
0 1 1 0 0 0
2 0 0 0 0 0
0 2 0 1 1 0

样例输出:

Case 1:
4

#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 99999999
using namespace std;
int map[205][205];
struct node
{
    int u,v,f;
};
node e[1000000];
int first[50000],next[1000000],cc;
int d[50000],gap[50000],curedge[50000],pre[50000];
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
inline void add_edge(int u,int v,int f)
{
    e[cc].u=u;
    e[cc].v=v;
    e[cc].f=f;
    next[cc]=first[u];
    first[u]=cc;
    cc++;

    e[cc].u=v;
    e[cc].v=u;
    e[cc].f=0;
    next[cc]=first[v];
    first[v]=cc;
    cc++;
};
int sap_max_flow(int s,int t,int n)
{
    int cur_flow=0,flow_ans=0,i,u,neck,tmp;
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    memset(pre,-1,sizeof(pre));
    for(i=0;i<=n;i++)
        curedge[i]=first[i];
    gap[0]=n+1;
    u=s;
    while(d[s]<n+1)
    {

        if(u==t)
        {
            cur_flow=inf;
            for(i=s;i!=t;i=e[curedge[i]].v)
            {
                if(cur_flow>e[curedge[i]].f)
                    cur_flow=e[curedge[i]].f,neck=i;
            }
            for(i=s;i!=t;i=e[curedge[i]].v)
            {
                tmp=curedge[i];
                e[tmp].f-=cur_flow;
                e[tmp^1].f+=cur_flow;
            }
            flow_ans+=cur_flow;
            u=neck;
        }
        for(i=curedge[u];i!=-1;i=next[i])
            if(e[i].f&&d[u]==d[e[i].v]+1)
                break;

        if(i!=-1)
        {
            curedge[u]=i;
            pre[e[i].v]=u;
            u=e[i].v;
        }
        else
        {
            if(0==--gap[d[u]])
                break;
            curedge[u]=first[u];
            for(tmp=n+5,i=first[u];i!=-1;i=next[i])
                if(e[i].f)
                    tmp=min(tmp,d[e[i].v]);
            d[u]=tmp+1;
            ++gap[d[u]];
            if(u!=s)
                u=pre[u];
        }
    }
    return flow_ans;

}
int main()
{
    int n,m;
    int tt=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;
        memset(map,0,sizeof(map));
        memset(e,0,sizeof(e));
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                scanf("%d",&map[i][j]);
        cc=0;
        int s=n*m;
        int t=n*m+1;
        memset(first,-1,sizeof(first));
        memset(next,-1,sizeof(next));
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                int k;
                for(k=0;k<4;k++)
                {
                    int tx=i+xx[k];
                    int ty=j+yy[k];
                    if(tx<0||tx>=n||ty<0||ty>=m)
                        continue;
                    add_edge(i*m+j,tx*m+ty,1);
                }
                if(map[i][j]==1)
                    add_edge(i*m+j,t,inf);
                if(map[i][j]==2)
                    add_edge(s,i*m+j,inf);
            }
        }
        printf("Case %d:\n",++tt);
        printf("%d\n",sap_max_flow(s,t,t));
    }
    return 0;
}

参考:http://blog.csdn.net/juststeps/article/details/8878022


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?