首页 > ACM题库 > HDU-杭电 > HDU 3395-Special Fish-网络流-[解题报告]HOJ
2014
03-23

HDU 3395-Special Fish-网络流-[解题报告]HOJ

Special Fish

问题描述 :

There is a kind of special fish in the East Lake where is closed to campus of Wuhan University. It’s hard to say which gender of those fish are, because every fish believes itself as a male, and it may attack one of some other fish who is believed to be female by it.
A fish will spawn after it has been attacked. Each fish can attack one other fish and can only be attacked once. No matter a fish is attacked or not, it can still try to attack another fish which is believed to be female by it.
There is a value we assigned to each fish and the spawns that two fish spawned also have a value which can be calculated by XOR operator through the value of its parents.
We want to know the maximum possibility of the sum of the spawns.

输入:

The input consists of multiply test cases. The first line of each test case contains an integer n (0 < n <= 100), which is the number of the fish. The next line consists of n integers, indicating the value (0 < value <= 100) of each fish. The next n lines, each line contains n integers, represent a 01 matrix. The i-th fish believes the j-th fish is female if and only if the value in row i and column j if 1.
The last test case is followed by a zero, which means the end of the input.

输出:

The input consists of multiply test cases. The first line of each test case contains an integer n (0 < n <= 100), which is the number of the fish. The next line consists of n integers, indicating the value (0 < value <= 100) of each fish. The next n lines, each line contains n integers, represent a 01 matrix. The i-th fish believes the j-th fish is female if and only if the value in row i and column j if 1.
The last test case is followed by a zero, which means the end of the input.

样例输入:

3
1 2 3
011
101
110
0

样例输出:

6

http://acm.hdu.edu.cn/showproblem.php?pid=3395

#include<iostream>
#include<queue>
using namespace std;
#define N 205
#define M 40005
int beg,end;
struct Graph    
{    
    struct node    
    {    
        int v,next,w,flow;    
        node(){};    
        node(int a,int b,int c,int d){    
            next=a;v=b;w=c;flow=d;    
        }    
    }E[2*M];    
    int head[N];    
    int pre[N];    
    int dis[N];    
    bool h[N];    
    int path[N];    
    int NE,NV;    
    void init(int n)    
    {    
        NE=0;    
        NV=n;    
        memset(head,-1,sizeof(head));    
    }    
    void insert(int u,int v,int w,int flow)    
    {    
        E[NE]=node(head[u],v,w,flow);    
        head[u]=NE++;    
        E[NE]=node(head[v],u,-w,0);    
        head[v]=NE++;    
    }    
    bool update(int u,int v,int w)    
    {    
        if(dis[u]+w>dis[v])    
        {    
            dis[v]=dis[u]+w;    
            return true;    
        }    
        return false;    
    }    
    bool spfa()    
    {    
        memset(pre,-1,sizeof(pre));    
        memset(h,0,sizeof(h));    
        for(int i=0;i<=NV;i++)
        	dis[i]=-0x7fff;
        dis[beg]=0;    
        queue<int> q;    
        q.push(beg);    
        while(!q.empty())    
        {    
            int u=q.front();    
            q.pop();    
            h[u]=0;    
            for(int i=head[u];i!=-1;i=E[i].next)    
            {    
                int v=E[i].v;    
                if(E[i].flow>0&&update(u,v,E[i].w))    
                {    
                    pre[v]=u;    
                    path[v]=i;    
                    if(!h[v])    
                    {    
                        h[v]=1;    
                        q.push(v);    
                    }    
                }    
            }    
        }    
        if(pre[end]==-1)    
            return false;    
        return true;    
    }    
    int maxcost_maxflow()    
    {    
        int flow=0;    
        int ans=0;
        while(spfa())    
        {    
            int Min=INT_MAX;    
            for(int i=end;i!=beg;i=pre[i])    
                if(Min>E[path[i]].flow)    
                    Min=E[path[i]].flow;    
            for(int i=end;i!=beg;i=pre[i])    
            {    
                E[path[i]].flow-=Min;    
                E[path[i]^1].flow+=Min;    
            }    
            flow+=Min;    
            ans+=dis[end];    
        }
        return ans;    
    }    
}G;
char map[101][105];
int main(void)
{
    int n;
    while(scanf("%d",&n),n)
    {
        beg=0;
        end=2*n+1;
        G.init(end);
        int val[101];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            G.insert(beg,i,0,1);
            G.insert(i,end,0,1);
            G.insert(i+n,end,0,1);
        }
        for(int i=1;i<=n;i++)
            scanf("%s",map[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(map[i][j]=='1')
                    G.insert(i,j+n,val[i]^val[j],1);
        printf("%d/n",G.maxcost_maxflow());
    }
}

 

http://hi.baidu.com/aekdycoin/blog/item/3bc9df1fa2327d1340341755.html~~~~~~

非常的直观。。。只能说网络流实在是太神奇,太灵活了~orz…..建图好难想,菜啊。。。

参考:http://blog.csdn.net/me4546/article/details/6412878


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.