poj 3189 二分+多重匹配

2010年11月08日 03:42

http://www.cublog.cn/u3/113538/showart_2212681.html

http://hi.baidu.com/scaneelingg/blog/item/a639111e08b98ac2a7866992.html

总是想不到二分.学到了多重匹配,X中一个点可以匹配Y中多个点,但Y中的点只能匹配一个X中的点.做法貌似是匈牙利算法的变种.也可以用最大流来做多重匹配,每一个X中的点连S,容量为1,每一个牛棚连T,容量为牛棚容量,XY之间按二分上下限连,但效率貌似要低.

#include <cstdio>
#include <cstring>

#define maxn 1001
#define maxm 21
int n,m;
//bool map[maxn][maxm];
int map[maxn][maxm];
int match[maxm][maxn];
bool v[maxm];
int cap[maxm];

int c[maxm];
int l,r;

int dfs(int p)
{
    int i,j;
    for(i=1;i<=m;i++)
        //if(map[p][i] && !v[i])
        if(l<=map[p][i] && map[p][i]<=r && !v[i])
        {
            v[i]=1;
            if(cap[i])
            {
                --cap[i];
                match[i][ ++match[i][0] ]=p;
                return 1;
            }
            else
            {
                for(j=1;j<=match[i][0];j++)
                    if(dfs(match[i][j]))
                    {
                        match[i][j]=p;
                        return 1;
                    }
            }
        }
    return 0;
}

int maxmatch()
{
    int i,ans=0;
    for(i=1;i<=m;i++)
        match[i][0]=0;
    for(i=1;i<=n;i++)
    {
        memset(v,false,sizeof(v));
        ans+=dfs(i);
    }
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,N,B,b;scanf("%d%d",&N,&B);
    for(i=1;i<=N;i++)
        for(j=1;j<=B;j++)
        {
            scanf("%d",&b);
            map[i][b]=j;
        }

    for(j=1;j<=B;j++)
        scanf("%d",&c[j]);

    l=r=1;
    int ans=B+1;
    while(l<=r && r<=B)
    {
        for(i=1;i<=B;i++) cap[i]=c[i];
        n=N;m=B;
        if(maxmatch()==N)
        {
            if(ans>r-l+1) ans=r-l+1;
            ++l;
        } else ++r;
    }
    printf("%d\n",ans);
}

话说从上次回来后就很久没做了,一直在忙落下的作业和实验,要坚持啊.

评论(0) 阅读(2535)

zju 3209 学习dancing links

2010年10月21日 04:10

用地图碎片完全覆盖大地图.每个地图碎片看作行,每个大地图里的格子看作一列,能覆盖则为1,然后DLX求精确覆盖.

#include <cstdio>
#include <cstring>
bool arr[601][1001];
#define MAX 0x3f3f3f3f
#define WID 1001
#define HGT 601
#define SIZE WID*(HGT+1)+10
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
    C[SIZE], Row[SIZE];//所在列 所在行
int S[WID + 10];
int sel[HGT],seln;//选择的列
int ans;

struct Dancer {
    int width, height;

    void init(int height,int width) {
        this->width = width;
        this->height = height;
        int p, x, y, last;
        for (x = 1; x <= width; x++) {//初始化列头指针
            L[x] = x - 1;
            R[x] = x + 1;
            U[x] = D[x] = x;
            S[x] = 0;//列元素
        }
        R[width] = 0;//0为总头指针
        p = width + 1;//每个节点编号
        for (y = 1; y <= height; y++) {//行
            last = R[0] = L[0] = 0;//作为每行虚拟头指针
            for (x = 1; x <= width; x++) {//列
                if (arr[y][x] != 0) {
                    U[p] = U[x];
                    C[p] = D[p] = x;
                    Row[p]=y;
                    L[p] = last;
                    S[x]++;
                    last = R[last] = U[x] = D[U[x]] = p++;
                }
            }
            R[last] = R[0];
            L[R[0]] = last;
        }
        L[0] = width;
        R[0] = 1;
        S[0] = MAX;
    }

    void remove(const int &c) {
        int i, j;
        L[R[c]] = L[c];//经典删除
        R[L[c]] = R[c];
        for (i = D[c]; i != c; i = D[i]) {
            for (j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --S[C[j]];
            }
        }
    }

    void resume(const int &c) {
        int i, j;
        for (i = U[c]; i != c; i = U[i]) {
            for (j = L[i]; j != i; j = L[j]) {
                ++S[C[j]];
                U[D[j]] = j;
                D[U[j]] = j;
            }
        }
        L[R[c]] = c;//经典恢复
        R[L[c]] = c;
    }

    bool dance() {
        if (R[0] == 0) return true;//空
        int c = 0, i, j;
        for (i = R[0]; i != 0; i = R[i])
            if (S[i] < S[c]) c = i;//元素最少的列
        remove(c);
        for (i = D[c]; i != c; i = D[i]) {//删除与c相连的行i
            sel[seln++]=Row[i];//选择此列 保存列号
            for (j = R[i]; j != i; j = R[j])//删除与i相连的列j
                remove(C[j]);
            //if (dance()) return true;
            if (dance()) {if(ans>seln) ans=seln;}
            for (j = L[i]; j != i; j = L[j])
                resume(C[j]);
            seln--;
        }
        resume(c);
        return false;
    }
};

#define get(x,y) m*x+y+1
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    Dancer dc;
    int n,m,c,i,j,k;
    int x1,y1,x2,y2;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d%d",&n,&m,&c);
        memset(arr,false,sizeof(arr));
        for(i=1;i<=c;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            for(j=x1;j<=x2-1;j++) for(k=y1;k<=y2-1;k++)
                arr[i][get(j,k)]=1;
        }
        ///////////////////
        seln=0;ans=MAX;
        dc.init(c,n*m);
        dc.dance();
        if(ans<MAX)
            printf("%d\n",ans);
        else printf("-1\n");
    }
}

nuaa 1507 http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507

重复覆盖的代码

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
#define N 70
#define INF 0x3f3f3f3f

int L[N*N],R[N*N],U[N*N],D[N*N],Y[N*N],Sum[N];
int n,m;
int ans;
bool hash[N];

void remove(int c)
{
    int i;
    for(i = D[c]; i != c; i = D[i])
    {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}

void resume(int c)
{
    int i;
    for(i = U[c]; i != c; i = U[i])
    {
        L[R[i]] = i;
        R[L[i]] = i;
    }

}

int h()
{
    int c,i,j,ret = 0;
    memset(hash,0,sizeof(hash));
    for(c = R[0]; c != 0; c = R[c])
    {
        if(!hash[c])
        {
            ret++;
            hash[c] = true;
            for(i = D[c]; i != c; i = D[i])
                for(j = R[i]; j != i; j = R[j])
                    hash[Y[j]] = true;
        }
    }
    return ret;
}

void dfs(int dep)
{
    int idx,i,j,Min = INF;
    if(dep+h() >= ans) return;
    if(R[0] == 0) {ans = dep; return;}
    for(i = R[0]; i != 0; i = R[i])
    {
        if(Sum[i] < Min)
        {
            Min = Sum[i];
            idx = i;
        }
    }
    for(i = D[idx]; i != idx; i = D[i])
    {
        remove(i);
        for(j = R[i]; j != i; j = R[j])
            remove(j);
        dfs(dep+1);
        for(j = L[i]; j != i; j = L[j])
            resume(j);
        resume(i);
    }

}

int main()
{
    int i,j,k,num;
    int head,tail,cnt;
    scanf("%d%d",&m,&n);
    for(i = 0; i <= m; i++)
    {
        L[i] = i-1; R[i] = i+1;
        U[i] = D[i] = i;
        Sum[i] = 0;
    }
    L[0] = m; R[m] = 0;
    cnt = m+1;
    for(i = 1; i <= n; i++)
    {
        head = tail = cnt;
        scanf("%d",&num);
        for(j = 1; j <= num; j++)
        {
            scanf("%d",&k);
            Sum[k]++;
            Y[cnt] = k;
            U[D[k]] = cnt;
            D[cnt] = D[k];
            U[cnt] = k;
            D[k] = cnt;
            L[cnt] = tail; R[tail] = cnt;
            R[cnt] = head; L[head] = cnt;
            tail = cnt; cnt++;
        }
    }
    ans = INF;
    dfs(0);
    if(ans == INF) ans = n;
    printf("%d\n",ans);
    return 0;
}

评论(0) 阅读(2143)

poj 2411 骨牌覆盖 dp

2010年10月18日 22:43

状态压缩的dp,强大的discuss.

如果是横着的就定义11,如果竖着的定义为竖着的01,这样按行dp只需要考虑两件事儿,当前行&上一行,是不是全为1,不是说明竖着有空(不可能出现竖着的00),另一个要检查当前行里有没有横放的,但为奇数的1 

	#include <cstdio>  
#include <cstring>  
int n,m;
int full;
long long dp[12][1<<11];

bool fit1(int j)
{
    int bits=0;
    while(j)
    {
        if(j&1) ++bits;
        else
        {
            if(bits&1) return 0;
            else bits=0;
        }
        j>>=1;
    }
    if(bits&1) return 0;
    return 1;
}
bool fit2(int j,int k)
{
    if((j|k)!=full) return 0;
    return fit1(j&k);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,k;
    while(scanf("%d%d",&n,&m),n)
    {
        if(n&m&1) {puts("0");continue;}
        full=(1<<m)-1;
        memset(dp,0,sizeof(dp));
        for(j=0;j<=full;j++)
            if(fit1(j))
                dp[1][j]=1;
        for(i=2;i<=n;i++)
        {
            for(j=0;j<=full;j++)
                for(k=0;k<=full;k++)
                    if(fit2(j,k)) dp[i][j]+=dp[i-1][k];
        }
        printf("%lld\n",dp[n][full]);
    }
}

评论(0) 阅读(2567)

hdu 1159 最长公共子序列

2010年10月17日 04:01

最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个数列 S ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

d[i][j]表示s1的第i位和s2的第j位之前的最长公共子序列长度.

转移方程:

d[i][j]=d[i-1][j-1]+1                  (s1[i-1]==s2[j-1])

d[i][j]=max(d[i-1][j],d[i][j-1])     (s1[i-1]<>s2[j-1])

评论(0) 阅读(2071)

poj 1077 康托展开

2010年10月10日 01:33

bfs,每个状态用康托展开来记录,用pre来记录上一个状态和避免重复搜索,顺便把方向记录在dir里,最后倒叙输出.

康托展开:得到某一排列是全排列从小到大的第几个,可以用来记录组合状态.

参考的:http://hi.baidu.com/mk%B5%C4%B4%B8%D7%D3/blog/item/4db13a16d7f4b00f4a90a7b7.html

#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
int fac[10];
int pre[400000];
char dir[400000];
void init()
{
    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
}

long cantor(int s[])
{
    int i,j,t;
    long num=0;
    for(i=0;i<9-1;i++)
    {
        t=0;
        for(j=i+1;j<9;j++)
            if(s[j]<s[i]) ++t;
        num+=fac[9-i-1]*t;
    }
    return num;
}
 
void uncantor(int s[],int ct)
{
    int i,j,t,r;
    bool p[10]={0};
    for(i=0;i<9;i++)
    {
        t=ct/fac[9-i-1]+1;
        ct%=fac[9-i-1];
        r=0,j=1;
        while(1)
        {
            if(!p[j]) r++;
            if(r==t) break;
            j++;
        }
        s[i]=j;p[j]=1;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    init();
    int tc[9];char c[2];
    int ot,t,i;bool ok=0;
    for(i=0;i<9;i++)
    {
        scanf("%s",c);
        if(c[0]=='x') tc[i]=9;
        else tc[i]=c[0]-'0';
    }

    memset(pre,0,sizeof(pre));
    queue<int> q;
    t=cantor(tc);pre[t]=-1;q.push(t);
    while(!q.empty())
    {
        ot=q.front();q.pop();
        if(ot==0) {ok=1;break;}

        uncantor(tc,ot);
        for(i=0;i<9;i++) if(tc[i]==9) break;
        //u
        if(i!=0&&i!=1&&i!=2)
        {
            swap(tc[i],tc[i-3]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='u';q.push(t);}
            swap(tc[i],tc[i-3]);
        }
        //d
        if(i!=6&&i!=7&&i!=8)
        {
            swap(tc[i],tc[i+3]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='d';q.push(t);}
            swap(tc[i],tc[i+3]);
        }
        //l
        if(i!=0&&i!=3&&i!=6)
        {
            swap(tc[i],tc[i-1]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='l';q.push(t);}
            swap(tc[i],tc[i-1]);
        }
        //r
        if(i!=2&&i!=5&&i!=8)
        {
            swap(tc[i],tc[i+1]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='r';q.push(t);}
            swap(tc[i],tc[i+1]);
        }
    }
    if(ok)
    {
        stack<char> s;
        while(pre[ot]!=-1)
        {
            s.push(dir[ot]);
            ot=pre[ot];
        }
        while(!s.empty())
        {printf("%c",s.top());s.pop();}
    }
    else printf("unsolvable");
    return 0;
}

评论(1) 阅读(2762)