The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

SGU 326 Perspective 网络流(经典竞赛问题)

题意:有n(<=20)只队伍比赛, 队伍i初始得分w[i], 剩余比赛场数r[i](包括与这n只队伍以外的队伍比赛), mat[i][j]表示队伍i与队伍j剩余比赛场数, 没有平局, 问队伍0有没有可能获得这n队中的第一名(可以有并列第一).

做法1:其实第一个队可以不用管它了,n支队我们将它压缩到n-1。
//球队编号[0,n-2]
//比赛数[n-1,n-2+id]
//超级源n-1+id
//超级汇n+id
//共n+id+1个点
把n-1只队伍作为顶点(把0号点去掉还剩n-1), 把(i<j)的所有场比赛作为顶点建图, 设i和j参加的比赛为c(i,j), 其数量为num(c(i,j)), 则i, j往c(i,j)连权值为num(c(i,j))的弧, c(i,j)往汇点也连权值为num(c(i,j))的弧, 超级源和每个队伍代表的顶点连流量是w[0]-w[i](w[0]是0号点赢得剩下所有比赛的得分),最大这样只要这条往汇点的弧满流, 则i, j赢的场数和一定为num(c(i,j)).


理解就是如果满流,那么所有的比赛可以安排,而且由于s->i已经控制了每个队可以赢得的比赛的上界,即使全部流到汇点也不会超过0号点的得分。

PS:我记得上次做了个浙大的题目,貌似和他很像,但是构图方法不一样,这题可以再研究下。


int mat[maxn][maxn];
int idx[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;



//球队编号[0,n-2]
//比赛数[n-1,n-2+id]
//超级源n-1+id
//超级汇n+id
//共n+id+1个点

//id中返回比赛数
int id;
int sum=0;
void input(int n)
{
    id
=0;
    sum
=0;
    memset(idx,
-1,sizeof(idx));

    
for(int i=0;i<n;i++)
        scanf(
"%d",&w[i]);
    
for(int i=0;i<n;i++)
        scanf(
"%d",&r[i]);
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
            scanf(
"%d",&mat[i][j]);

    
//
    /*
    for(int i=1;i<n;i++)
        w[0]+=mat[0][i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            r[i]-=mat[i][j];
        }
        
*/

    w[
0]+=r[0];
    
//剩下i对外区比赛场次

    
for(int i=1;i<n;i++)
        
for(int j=i+1;j<n;j++)
        
{
            idx[i][j]
=id++;
            sum
+=mat[i][j];
        }

    s
=n-1+id;
    t
=n+id;
}






int main()
{
    scanf(
"%d",&n);
    input(n);
    
for(int i=0;i<n+id+1;i++)
        adj[i]
=NULL;
    len
=0;
    
//
    for(int i=1;i<n;i++)
        
for(int j=i+1;j<n;j++)
        
{
                insert(i
-1,idx[i][j]+n-1,mat[i][j]);
                insert(j
-1,idx[i][j]+n-1,mat[i][j]);
                insert(idx[i][j]
+n-1,t,mat[i][j]);
        }

    
for(int i=1;i<n;i++)
        
if(w[0]<w[i])
        
{
            printf(
"NO\n");
            
return 0;
        }

    
for(int i=1;i<n;i++)
        insert(s,i
-1,w[0]-w[i]);
    
    
if(sap(n+id+1,s,t)==sum)
        printf(
"YES\n");
    
else
        printf(
"NO\n");
    
return 0;
}



做法二: 这个构图更为简单直观(不容易错),不需要再建立比赛的节点,结点数O(n).
具体构图方法见http://www.cppblog.com/abilitytao/archive/2010/07/21/120933.html

int mat[maxn][maxn];
int n;
int w[maxn];
int r[maxn];
int s,t;




//超级源0
//超级汇n
//共n+1个点

int sum;
void input(int n)
{

    sum
=0;
    
for(int i=0;i<n;i++)
        scanf(
"%d",&w[i]);
    
for(int i=0;i<n;i++)
        scanf(
"%d",&r[i]);
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
            scanf(
"%d",&mat[i][j]);
    w[
0]+=r[0];
    
//剩下i对外区比赛场次
    s=0;
    t
=n;

}






int main()
{
    scanf(
"%d",&n);
    input(n);
    
for(int i=0;i<n+1;i++)
        adj[i]
=NULL;
    len
=0;
    
//
    int arr[maxn];
    memset(arr,
0,sizeof(arr));
    
for(int i=1;i<n;i++)
    
{
        
for(int j=i+1;j<n;j++)
        
{
            arr[i]
+=mat[i][j];
            sum
+=mat[i][j];
        }

        insert(s,i,arr[i]);
    }

    
    
for(int i=1;i<n;i++)
        
if(w[0]<w[i])
        
{
            printf(
"NO\n");
            
return 0;
        }

    
    
for(int i=1;i<n;i++)
        insert(i,t,w[
0]-w[i]);

    
for(int i=1;i<n;i++)
    
{
        
for(int j=i+1;j<n;j++)
        
{
            insert(i,j,mat[i][j]);
        }

    }

    
    
if(sap(t+1,s,t)==sum)
        printf(
"YES\n");
    
else
        printf(
"NO\n");
    
return 0;
}

posted on 2010-11-12 01:03 abilitytao 阅读(604) 评论(0)  编辑 收藏 引用


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