hdu 3663 精确覆盖 dlx

2011年9月19日 15:47

此文充数.去年哈尔滨的D,残念啊伤心.

一些城市,每个都有电厂,既为自己供电,同时又为直接相邻的城市供电,但是供电有时间限制,而且同一城市不能有两处供电来源.求一个方案.

现在来看还是比较清晰的精确覆盖,有了数独的经验就知道用行来记录结果,用列来避免碰撞,所以拿电厂和发电时间去匹配城市和天数.转化也还算好想,发电时间枚举区间即可,但是题目有个限制,最后方案中的每个电厂的发电时间不能是离散区间,所以要加几列碰撞,使得每个电厂只能选一个发电区间,还要加一个发电区间表示电厂不发电,这几个点不太好想.转化好最后套进模板就出来了(我的模板的行列都是从1开始的,所以我把城市号处理成从0开始的了).

#include<cstdio>
#include<algorithm>
using namespace std;
#include<cstdlib>
#include<cstring>

bool mm[60][60];
int dd[60][2];
int q[16][2],top;

#define MAX 0x7fffffff
#define MAXR 4000
#define MAXC 700
bool arr[MAXR][MAXC];
#define SIZE MAXR*MAXC
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
    Col[SIZE], Row[SIZE];//所在列 所在行
int S[MAXC]; //列元素数
int sel[MAXR],seln;//选择的行

struct Dancer
{
    void init(int height,int width)
    {
        int p, x, y, last;
        for (p = 1; p <= width; p++)
        {
            L[p] = p - 1; R[p] = p + 1;
            U[p] = D[p] = p;
            S[p] = 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)
                {
                    L[p] = last; R[last] = p;
                    U[p] = U[x]; D[p] = x; U[x] = D[U[x]] = p;
                    Row[p]=y; Col[p]=x;
 
                    S[x]++; last=p++;
                }
            }
            R[last] = R[0]; L[R[0]] = last;
        }
        R[width] = 0; L[0] = width; R[0] = 1;
        S[0] = MAX;
    }
  
    void remove(const int &c)
    {
        L[R[c]] = L[c]; R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j])
            {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --S[Col[j]];
            }
    }
  
    void resume(const int &c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
            {
                U[D[j]] = j;
                D[U[j]] = j;
                ++S[Col[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])
        {
            for (j = R[i]; j != i; j = R[j])
                remove(Col[j]);
            sel[seln]=Row[i];
            seln++;
            if (dance()) return true;
            seln--;
            for (j = L[i]; j != i; j = L[j])
                resume(Col[j]);
        }
        resume(c); return false;
    }
} dc;
/////////////////////////////////////////////////////////////

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,d;
    while(scanf("%d%d%d",&n,&m,&d)!=EOF)
    {
        //all internals
        top=1;
        for(int i=1;i<=5;i++) for(int j=i;j<=5;j++)
            q[top][0]=i,q[top++][1]=j;
        
        memset(mm,false,sizeof(mm));
        for(int i=0;i<n;i++) mm[i][i]=1;
        for(int i=0;i<m;i++)
        {
            int a,b; scanf("%d%d",&a,&b);
            a--;b--;
            mm[a][b]=mm[b][a]=1;
        }
        
        for(int i=0;i<n;i++)
            scanf("%d%d",&dd[i][0],&dd[i][1]);
        //转化
        memset(arr,false,sizeof(arr));
        for(int i=0;i<n;i++)//each power station
        {
            for(int k=0;k<top;k++)//each internal
            {
                int r=i*top+k+1;//station i work on internal k
                arr[r][n*d+i+1]=1;//station collision
                int d1=q[k][0],d2=q[k][1];
                if(k==0) continue;//not work
                if(d1<dd[i][0] || d2>dd[i][1])//bad date
                    continue;
                for(int j=0;j<n;j++) if(mm[i][j])//each city
                    for(int di=d1;di<=d2;di++)
                    {
                        int c=j*d+di;
                        arr[r][c]=1;//soga
                    }
            }
        }
        //dance
        seln=0; dc.init(n*top,n*d+n);
        if(!dc.dance())
            puts("No solution");
        else
        {
            for(int i=0;i<seln;i++)//get data from line number
            {
                int s=(sel[i]-1)/top;//station
                int k=(sel[i]-1)%top;
                dd[s][0]=q[k][0]; dd[s][1]=q[k][1];//record
            }
            for(int i=0;i<n;i++)
                printf("%d %d\n",dd[i][0],dd[i][1]);
        }
        putchar('\n');
    }
}

评论(0) 阅读(1292)

字典序生成r组合

2011年8月13日 17:05

# coding: utf-8

 ## n
#
 ## m

m=9
n=3
a=[i for i in range(n)]
ma=[m-n+i for i in range(n)] # 最大的一组

count=0

while 1:
    count+=1
    print a
    found=False
    for i in range(n)[::-1] : # 从后往前找可增的
        if a[i]<ma[i]:
            a[i]+=1
            for j in range(i+1,n): # 其后的按字典序初始化
                a[j]=a[j-1]+1
            found=True
            break
    if not found: break

print 'count:',count

评论(0) 阅读(1261)

poj 3076 dancing links 解n*n的数独

2011年7月04日 15:44

原来dancing links解数独也是把数独转换为精确覆盖问题.

精确覆盖问题是指一个01矩阵,选择某些行使得每一列都有且只有一个1(既选行精确覆盖列).

(1)设问题为m^2 * m^2的规模,且n=m^2,则矩阵大小为n*n.

(2)用行来记录选出的结果,既第i行j列填k,使用n进制,所以行号为n*n*i + n*j + k.

输入时若M[i][j]为空,则k可取1~9,否则k只能取M[i][j].

(3)用列来避免碰撞,把列分为四个区:

[0~1*n*n)是第i,j行是否有数,所以其序号为n*i+j

[1*n*n~2*n*n)是第i行是否有k,所以其序号为n*i+k

[2*n*n~3*n*n)是第j列是否有k,所以其序号为n*j+k

[3*n*n~4*n*n)是第b个盒子(m*m)是否有k,所以其序号为n*b+k

(3)对每一个可取的行,设置对应的四个列为1,就构造好了,然后代到dancing links解精确覆盖的模板里解出来,把选择的行号(共n*n个)按照n进制解析出来就知道在M[i,j]填几(k)了.

因为模板里,行列都是从1开始的,所以叹号处有一些诡异的转换......

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define MAX 0x3f3f3f3f
#define MAXM 4
#define MAXN MAXM*MAXM
#define MAXR MAXN*MAXN*MAXN+20
#define MAXC 4*MAXN*MAXN+20
int M[MAXN][MAXN];
bool arr[MAXR][MAXC];
#define SIZE MAXR*MAXC
int L[SIZE], R[SIZE], U[SIZE], D[SIZE],
    Col[SIZE], Row[SIZE];//所在列 所在行
int S[MAXC]; //列元素数
int sel[MAXR],seln;//选择的行
 
struct Dancer 
{
    void init(int height,int width) 
    {
        int p/*节点编号*/, x, y, last;
        for (p = 1; p <= width; p++) //初始化列头指针
        {
            L[p] = p - 1; R[p] = p + 1; //左右相邻
            U[p] = D[p] = p; //只有一列
            S[p] = 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-1][x-1] != 0)  // 0~n-1 -> 1~n !!!!!!!!!!!!!!!
                {
                    //添到行链表尾部
                    L[p] = last; R[last] = p;
                    //添到列链表尾部
                    U[p] = U[x]; D[p] = x; U[x] = D[U[x]] = p;
                    ////记录所在行列
                    Row[p]=y; Col[p]=x;

                    S[x]++; last=p++;
                }
            }
            // 去虚头,构成行循环链表
            R[last] = R[0]; L[R[0]] = last;
        }
        R[width] = 0; L[0] = width; R[0] = 1;
        S[0] = MAX;
    }
 
    //删除c列上所有1元素所在的行
    void remove(const int &c) 
    {
        L[R[c]] = L[c]; R[L[c]] = R[c];//经典删除
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j])
            {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --S[Col[j]];
            }
    }
 
    //恢复c列上所有1元素所在的行
    void resume(const int &c) 
    {
        for (int i = U[c]; i != c; i = U[i]) 
            for (int j = L[i]; j != i; j = L[j]) 
            {
                U[D[j]] = j;
                D[U[j]] = j;
                ++S[Col[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])//找元素最少的列c
            if (S[i] < S[c]) c = i;
        remove(c);
        for (i = D[c]; i != c; i = D[i])//删除与c相连的行i
        {
            for (j = R[i]; j != i; j = R[j])//删除行元素所在的列j
                remove(Col[j]);
            sel[seln]=Row[i];//选择此行 保存行号
            seln++;
            if (dance()) return true;
            seln--;
            for (j = L[i]; j != i; j = L[j])
                resume(Col[j]);
        }
        resume(c); return false;
    }
} dc;

///////////////////////////////////////////////////////////////
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j,k,m=4,n=16;
    char c;

    while((c=getchar())!=EOF)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(c=='\n') c=getchar();
                M[i][j]=(c=='-')?0:c-'A'+1;//!!!
                c=getchar();
            }
        }

        memset(arr,false,sizeof(arr));
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                int b=i/m*m+j/m;//i,j的盒子号
                if(M[i][j]==0)
                {
                    for(k=0;k<n;k++)
                    {
                        int r=n*n*i+n*j+k;
                        arr[r][0*n*n + n*i+j ]=1;//i,j里有数
                        arr[r][1*n*n + n*i+k ]=1;//i行里有k
                        arr[r][2*n*n + n*j+k ]=1;//j列里有k
                        arr[r][3*n*n + n*b+k ]=1;//b盒里有k
                    }
                }
                else
                {
                    k=M[i][j]-1;//!!!
                    int r=n*n*i+n*j+k;
                    arr[r][0*n*n + n*i+j ]=1;//i,j里有数
                    arr[r][1*n*n + n*i+k ]=1;//i行里有k
                    arr[r][2*n*n + n*j+k ]=1;//j列里有k
                    arr[r][3*n*n + n*b+k ]=1;//b盒里有k
                }
            }

        ///////////////////////////////////
        seln=0;
        dc.init(n*n*n,n*n*4);
        if(dc.dance())
        {
            for(int h=0;h<seln;h++)
            {
                int t=sel[h]-1;//!!!
                k=t%n; t/=n;
                j=t%n; t/=n;
                i=t%n;
                M[i][j]=k;//!!!
            }
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                    putchar('A'+M[i][j]);
                putchar('\n');
            }
        }
        else
            puts("INCORRECT");
        putchar('\n');
    }
}

评论(0) 阅读(3008)

nlogn的最长不下降子序列

2011年4月17日 00:58

做做dp,记下来,开始真是连dp都没想出来,由于数字只有1和2(poj 3671),写了个分治居然过了
搜了搜写O(n^2)的LIS果断超了,只好找资料,才知道只求长度的话有nlogn的LIS:
  使用d[j]来记录 长度为j的不减序列的最后一个元素 的值中的最小值,k为d数组的长度,初始可以为1,随着从前往后扫描输入数组a慢慢增长:
    1.若a[i]>=d[k],可以扩展了,d[++k]=a[i]

    2.若a[i]<d[1],则d[1]=a[i]

    3.否则,二分(易证明d为不减序列)找到d[1...k]中最大的j使d[j]<=a[i],因为d[j+1]>=d[j]>=a[i],所以更新d[j+1]=a[i]

最后k就是LIS的长度了

ref:这篇吴豪大牛的这篇

评论(0) 阅读(2070)

poj 2762 半连通图判断

2011年3月22日 19:59

昨天算法课讲了强连通kosaraju算法,今天做课后题看到半连通问题,好久没做题了,就想写一写,证明自己的一些想法,结果悲剧了,各种无语的小错误......

题意其实就是判断图是否是半连通的,强连通缩点后:

1.拓扑排序判断每次队列中是否只有一个元素,看来的

#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
using namespace std;

int T,n,m;
bool vit[1001];
int ind[1001];
int mark[1001],scc;
deque<int> f;
vector<int> g[1001];
vector<int> gt[1001];
bool chong[1001][1001];
vector<int> *gs=gt;
void dfs(int s);
void dfsmain()
{
    memset(vit,false,sizeof(vit));
    f.clear();
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
}
void dfs(int s)
{
    vit[s]=1;
    for(unsigned i=0;i<g[s].size();i++)
        if(!vit[g[s][i]]) dfs(g[s][i]);
    f.push_front(s);
}
void tdfs(int s);
void tdfsmain()
{
    memset(mark,0,sizeof(mark));scc=0;
    memset(vit,0,sizeof(vit));
    while(!f.empty())
    {
        int u=f.front();f.pop_front();
        if(!vit[u])
            ++scc,tdfs(u);
    }
}
void tdfs(int s)
{
    vit[s]=1;mark[s]=scc;
    for(unsigned i=0;i<gt[s].size();i++)
        if(!vit[gt[s][i]]) tdfs(gt[s][i]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            g[i].clear(),gt[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            gt[v].push_back(u);
        }
        dfsmain();
        tdfsmain();
        //for(int i=1;i<=n;i++)
            //printf("%d ",mark[i]);
        //puts("");

        memset(ind,0,sizeof(ind));
        memset(chong,0,sizeof(chong));
        for(int i=1;i<=scc;i++)
            gs[i].clear();
        for(u=1;u<=n;u++)
            for(unsigned i=0;i<g[u].size();i++)
            {
                v=g[u][i];
                if(mark[u]!=mark[v] && !chong[mark[u]][mark[v]])
                    gs[mark[u]].push_back(mark[v]),
                        ind[mark[v]]++, chong[mark[u]][mark[v]]=1;
            }
        deque<int> q;
        for(int i=1;i<=scc;i++)
            if(!ind[i])
                q.push_back(i);
        bool failed=0;
        while(!q.empty())
        {
            if(q.size()!=1)
            {failed=1; break;}
            int u=q.front();q.pop_front();
            for(unsigned i=0;i<gs[u].size();i++)
            {
                int v=gs[u][i];
                if(--ind[v]==0)
                    q.push_back(v);
            }
        }
        if(failed)
            puts("No");
        else
            puts("Yes");
    }
}

2.或者直接dfs狂搜(不管是否已vit),得到dfs的最大深度,是否等于点数,看所有点是否能在一条路上,代码好写.

#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
using namespace std;

int T,n,m;
bool vit[1001];
int ind[1001];
int mark[1001],scc;
deque<int> f;
vector<int> g[1001];
vector<int> gt[1001];
bool chong[1001][1001];
vector<int> *gs=gt;
void dfs(int s);
void dfsmain()
{
    memset(vit,false,sizeof(vit));
    f.clear();
    for(int i=1;i<=n;i++)
        if(!vit[i]) dfs(i);
}
void dfs(int s)
{
    vit[s]=1;
    for(unsigned i=0;i<g[s].size();i++)
        if(!vit[g[s][i]]) dfs(g[s][i]);
    f.push_front(s);
}
void tdfs(int s);
void tdfsmain()
{
    memset(mark,0,sizeof(mark));scc=0;
    memset(vit,0,sizeof(vit));
    while(!f.empty())
    {
        int u=f.front();f.pop_front();
        if(!vit[u])
            ++scc,tdfs(u);
    }
}
void tdfs(int s)
{
    vit[s]=1;mark[s]=scc;
    for(unsigned i=0;i<gt[s].size();i++)
        if(!vit[gt[s][i]]) tdfs(gt[s][i]);
}
int maxl;
void finaldfs(int s,int l)
{
    if(l>maxl) maxl=l;
    for(unsigned i=0;i<gs[s].size();i++)
        finaldfs(gs[s][i],l+1);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            g[i].clear(),gt[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            gt[v].push_back(u);
        }
        dfsmain();
        tdfsmain();
        //for(int i=1;i<=n;i++)
            //printf("%d ",mark[i]);
        //puts("");

        memset(ind,0,sizeof(ind));
        memset(chong,0,sizeof(chong));
        for(int i=1;i<=scc;i++)
            gs[i].clear();
        for(u=1;u<=n;u++)
            for(unsigned i=0;i<g[u].size();i++)
            {
                v=g[u][i];
                if(mark[u]!=mark[v] && !chong[mark[u]][mark[v]])
                    gs[mark[u]].push_back(mark[v]),
                        ind[mark[v]]++, chong[mark[u]][mark[v]]=1;
            }
        maxl=0;
        for(int i=1;i<=scc;i++)
            if(!ind[i])
                finaldfs(i,1);
        if(maxl==scc)
            puts("Yes");
        else
            puts("No");
    }
}

 

评论(0) 阅读(2536)