hdu 1569 方格取数

2010年9月01日 23:09

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

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

构图:

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

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

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

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

分析:

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

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

评论(0) 阅读(2166)

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) 阅读(1837)

SPFA的两个优化(转)

2010年8月26日 08:36

转自:http://aceeca1.frostbytez.com/index.php/archives/SPFA%E4%BC%98%E5%8C%96

  SLF:Small Label First 策略。
实现方法是,设队首元素为 $i$,队列中要加入节点 $j$,在 $d_j \le d_i$ 时加到队首而不是队尾,否则和普通的 SPFA 一样加到队尾。

  LLL:Large Label Last 策略。
实现方法是,设队列 $Q$ 中的队首元素为 $i$,距离标号的平均值为 $\overline d = \frac {\sum_{j \in Q} d_j }{\left| Q \right|}$,每次出队时,若 $d_i > \overline d$,把 $i$ 移到队列末尾,如此反复,直到找到一个 $i$ 使 $d_i \le \overline d$,将其出队。

评论(0) 阅读(2915)

POJ 3660 传递闭包 warshall算法

2010年8月16日 19:31

  初始化为-1,计算传递闭包过程中赢记为1,输记为0,最后检查传递闭包中无-1的行数或列数。

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int adj[101][101];
int tc[101][101];

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m,v,w,i,s,t,ans;
    scanf("%d%d",&n,&m);
    memset(adj,-1,sizeof(adj));
    for(i=1; i<=n; i++) adj[i][i]=1;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&v,&w);
        adj[v][w]=1;
    }

    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            tc[s][t]=adj[s][t];

    for(i=1;i<=n;i++)
        for(s=1;s<=n;s++)
            if(tc[s][i]>0)
                for(t=1;t<=n;t++)
                    if(tc[i][t]>0) {tc[s][t]=1;tc[t][s]=0;}

//    for(s=1; s<=n; s++)
//    {
//        for(t=1; t<=n; t++)
//            printf("%3d ",tc[s][t]);
//        cout<<endl;
//    }

    ans=n;
    for(s=1; s<=n; s++)
        for(t=1; t<=n; t++)
            if(tc[s][t]==-1)
            {
                ans--;
                break;
            }
    printf("%d\n",ans);
    return 0;
}

 

评论(0) 阅读(1281)

poj 3270 置换,循环节

2010年8月10日 23:11

firefox崩溃了,害我打的字儿没了……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int cow[10001];
int scow[10001];
int pos[100001];
bool hasg[10001];

int main()
{
    freopen("in","r",stdin);
    int n,allmin,gsum,glen,gmin,tans,ans;
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",cow+i);
        scow[i]=cow[i];
    }
    sort(scow,scow+n);
    allmin=scow[0];
    for(i=0;i<n;i++)
        pos[scow[i]]=i;

    memset(hasg,0,sizeof(bool)*n);

    ans=0;
    for(int i=0;i<n;i++)
    {
        if(!hasg[i])//new group
        {
            hasg[i]=1;
            gsum=cow[i];glen=1;gmin=cow[i];
            j=i;
            while(!hasg[pos[cow[j]]])
            {
                j=pos[cow[j]];
                hasg[j]=1;
                gsum+=cow[j];
                ++glen;
                if(gmin>cow[j]) gmin=cow[j];
            }

            tans=min(gsum+(glen-2)*gmin,
                    gsum+gmin+(glen+1)*allmin);
            ans+=tans;
        }
    }
    printf("%d",ans);
}

 

评论(0) 阅读(1140)