• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            PKU 3854 搜索、然后進行類似拓撲排序的處理

            這題大意是一堆積木,抽掉某一塊后會使得上面的積木崩潰(當上面的積木僅僅與抽去的部分相鄰),問抽去哪塊積木會使得崩塌的總積木數(shù)最多
            這題做法是先將積木處理成圖的節(jié)點,然后如果假設底下的積木i與上面的積木j直接相鄰面為k,則將i與j連接條權(quán)值為k的邊,然后針對每一塊積木枚舉求崩潰的總塊數(shù),這里用類似拓撲排序算法的處理,將每個節(jié)點底面與其他面的接觸面數(shù)作為該節(jié)點的“入度”

             1# include <iostream>
             2using namespace std;
             3# include <cstdio>
             4# include <map>
             5# include <cstring>
             6# include <vector>
             7# include <queue>
             8char g[101][101];
             9int id[101][101];
            10int n,m,c;
            11# define max(a,b) ((a)>(b)?(a):(b))
            12struct
            13{
            14    int r,c,len;
            15}
            block[10001];
            16int main()
            17{
            18    while(true)
            19    {
            20        scanf("%d%d",&n,&m);
            21        if(!n&&!m) break;
            22        for(int i=0;i<n;i++)
            23            scanf("%s",g[i]);
            24        c=0;
            25        for(int i=0;i<n;i++)
            26            for(int j=0;j<m;)
            27            {
            28                if(g[i][j]=='0')
            29                {
            30                    j++;
            31                    continue;
            32                }

            33                block[c].r=i;
            34                block[c].c=j;
            35                block[c].len=g[i][j]-'0';
            36                for(int k=j;k<block[c].len+j;k++)
            37                     id[i][k]=c;
            38                j+=block[c++].len;
            39            }

            40        int degree[10001];
            41        int res=0;
            42        queue<int> q;
            43        int stddegree[10001];
            44        for(int i=0;i<c;i++)
            45        {
            46            stddegree[i]=block[i].len;
            47            if(block[i].r+1!=n)
            48                for(int j=block[i].c;j<block[i].c+block[i].len;j++)
            49                    if(g[block[i].r+1][j]=='0')
            50                        stddegree[i]--;
            51        }

            52        for(int i=0;i<c;i++)
            53        {
            54
            55            int ans=0;
            56            memcpy(degree,stddegree,sizeof(degree));
            57            q.push(i);
            58            while(!q.empty())
            59            {
            60                int top=q.front();
            61                q.pop();
            62                ans+=block[top].len;
            63                if(block[top].r!=0)
            64                    for(int j=block[top].c;j<block[top].c+block[top].len;j++)
            65                    if(g[block[top].r-1][j])
            66                    {
            67                        degree[id[block[top].r-1][j]]--;
            68                        if(!degree[id[block[top].r-1][j]])
            69                            q.push(id[block[top].r-1][j]);
            70                    }

            71            }

            72            res=max(res,ans);
            73        }

            74        printf("%d\n",res);
            75
            76
            77    }

            78    return 0;
            79}

            80
            81
            82

            posted on 2010-10-14 18:13 yzhw 閱讀(207) 評論(0)  編輯 收藏 引用 所屬分類: searchgraph

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久99精品久久久久久齐齐| 99精品国产综合久久久久五月天 | 精品无码久久久久久国产| 99久久免费只有精品国产| 久久久久久久综合综合狠狠| 久久国产美女免费观看精品| 一本久久综合亚洲鲁鲁五月天| 久久久久久久久久久精品尤物| 国内精品久久久久久久97牛牛| 国产精品美女久久久久AV福利| 国产一区二区久久久| 亚洲国产成人久久精品动漫| 欧美日韩久久中文字幕| 精品久久久久久国产牛牛app| 久久综合狠狠综合久久| 亚洲国产精品狼友中文久久久 | 国产精品久久久久久久久软件| 国产精品视频久久久| 亚洲国产日韩综合久久精品| 久久九九亚洲精品| 少妇久久久久久久久久| 精品久久久一二三区| 久久精品无码一区二区三区日韩 | 国产精品福利一区二区久久| 久久香综合精品久久伊人| 久久久99精品成人片中文字幕 | 国产亚洲综合久久系列| yy6080久久| 久久精品桃花综合| 中文字幕久久亚洲一区| 日本精品久久久久影院日本 | 久久亚洲精品国产精品| 亚洲欧美伊人久久综合一区二区 | 国内精品人妻无码久久久影院| 久久久国产打桩机| 久久久久亚洲精品日久生情| 97精品伊人久久大香线蕉| 狠狠色丁香婷婷久久综合五月| 久久99这里只有精品国产| 久久综合九色综合网站| 亚洲国产精品无码久久一区二区|