posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3491感谢c j同学的帮助

Posted on 2010-08-15 20:50 acronix 阅读(233) 评论(0)  编辑 收藏 引用 所属分类: qqy解题报告

//考察点: 拆点 + 最大流

//思路: 把城市作为点拆开(把城市i拆成cap数组中的cap[i][i+n].其中i作为城市i的入,i+n作为城市i的出),原来的街道仍然作为边,但是边权是无穷大. 只要注意到BFS的时候 起点/终点是不需要拆的.(cap[][]数组中就直接把起点/终点的入和出之间的边权赋值为0,使得BFS的时候不走起点/终点,实际上就相当于没有把起点/终点拆开.程序中的处理方法就是 cap[s][s+n] = 0;/cap[e][e+n] = 0;)

//提交情况; Wrong Answer 4 Accepted 1

WA 的原因是: BFS写错 做完一个CASE没有初始化cap数组导致错误

//收获: BFS有了更深的理解 对抽象出来的算法过程也有了具体的体会   吸取了不初始化的教训

//经验: 在学习一个代码的时候要手动模拟一下过程 好好理解算法的精髓 另外要加强联系 争取掌握用邻接表建图的方法

//ACcode

#include<stdio.h>
#include
<memory.h>
#include
<stdlib.h>
const int INF = 0x7fffffff;
int cap[201][201];
int s,t;
int que[201],pre[201];
int n,m;
bool vis[201];
bool findroad()
{
    memset(vis,
0,sizeof(vis));
    
int i,j;
    
int head = 0,tail = 0;
    que[tail 
++= s;
    
while(head < tail)
    {
        j 
= que[head ++];
        
for(i = 1; i <= 2*n ;i ++)
        {
            
if(!vis[i] && cap[j][i] > 0)
            {
                vis[i] 
= true;
                pre[i] 
= j;
                
if(i == t) return true;
                que[tail 
++= i;
            }
        }
    }
    
return false;
}
int maxflow()
{

    int flow = 0,i,min;
    
while(findroad())
    {
        min 
= INF;
        
for(i = t; i != s;i = pre[i])
        {
            
if(cap[pre[i]][i] < min)
                    min 
= cap[pre[i]][i];
        }
        flow 
+= min;
        
for(i = t; i != s;i = pre[i])
        {
            cap[pre[i]][i] 
-= min;
            cap[i][pre[i]] 
+= min;
        }
    }
    
return flow;
}
int main()
{
    
int T,x,y,i,j,tem,b,e;
    scanf(
"%d"&T);
    
while(T--)
    {
        scanf(
"%d%d%d%d",&n,&m,&b,&e);
        
for(i = 1; i <= n;i ++)
        {
            scanf(
"%d",&tem);
            cap[i][i
+n] = tem;
        }
        s 
= b + n;
        t 
= e;
       cap[e][e
+n]=0;
        cap[s][s
+n]=0;
        
for(i = 1; i <= m;i ++)
        {
            scanf(
"%d%d",&x,&y);
            cap[x
+n][y] = INF;
            cap[y
+n][x] = INF;
        }
        printf(
"%d\n",maxflow());
        memset(cap,
0,sizeof(cap));
    }
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理