• <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>
            posts - 7,comments - 3,trackbacks - 0
            Electricity

            Time Limit: 10 Seconds      Memory Limit: 32768 KB      Special Judge

            After recent blackouts in some regions in North America, the government has decided to reorganize the power supply network of the continent.

            The power supply network is the set of nodes, such as power plants or transformation stations, connected by transmission lines. All lines are used to transmit electricity from one node to another. For stability reasons the system is organized in such a way that there are no directed cycles.

            Since the government is currently short of money due to several small peaceful militaristic operations, it cannot build new power lines for the moment. So after reorganization the same lines will be used, but some lines will have to transmit electricity in the direction opposite to the current one. To make the reorganization gentle enough, the management of the power network is planning to switch the transmission direction for exactly one line each day. Of course, no day there must be a cycle in a network, since this may cause damage to the system. The resulting network is also designed to be acyclic.

            Help them to plan the reorganization.

            Input

            There are mutilple cases in the input file.

            The first line of the input file contains n --- the number of nodes in the network, and m --- the number of transmission lines (2 <= n <= 1,000 , 1 <= m <= 10,000 ). The following m lines contain three integer numbers each. The first two give the source and the destination node for the corresponding line in the current node. The third number is 0 if the line must keep its transmission direction in the resulting network, and 1 if the direction must be reversed.

            There can be several lines connecting the same pair of nodes, but due to acyclicity condition, they all transmit electricity in the same direction. This is also the reason why no line connects a node to itself.

            There is an empty line after each case.

            Output

            First output k --- the number of days in the plan you suggest. You don't need to minimize this number, but it must not exceed 4m . After that print k integer numbers --- for each day output the number of the line that changes the transmission direction this day. If it is impossible to make the desired reorganization, output -1 instead of k .

            There should be an empty line after each case.

            Sample Input

            4 5
            1 2 0
            2 3 1
            2 4 1
            1 4 1
            4 3 0
            
            2 2
            1 2 1
            1 2 1
            
            

            Sample Output

            3
            3 2 4
            
            -1
            
            

            Source: Andrew Stankevich's Contest #9


            一道不錯的圖論題,大意是給一個有向網(wǎng)絡(luò)N,必須將其中X條邊反向,給出一個方案順序,使得在執(zhí)行反向的過程中,網(wǎng)絡(luò)不會出現(xiàn)環(huán),如果不存在這個方案,輸出-1.

            思路:首先,判斷不存在的情況:1.兩個重邊都要反轉(zhuǎn),那么在操作過程中肯定出現(xiàn)環(huán);2.在初始網(wǎng)絡(luò)或結(jié)束網(wǎng)絡(luò)存在環(huán)。對于第二種情況,可以用topo排序求一下兩個網(wǎng)絡(luò)是否存在環(huán),并記錄下topp序列。
            之后,我們要構(gòu)造方案,構(gòu)造方案的過程有兩個:
            1.一個點的可逆入度邊(這句是廢話,可逆邊就是必須改變的邊,肯定包含于方案,但注意是入度)
            2.這個點必須從結(jié)尾網(wǎng)絡(luò)的topo序列從后往前搜索.....(凌亂了吧....)
            首先,我們要明白topo序列的性質(zhì),就是序列a1,a2,a3,...,an,表示的是網(wǎng)絡(luò)n個點的線性關(guān)系,存在任意的i<j,使得ai -> aj,也就是,如果用網(wǎng)絡(luò)表示topo序列,那么只有往右邊指向的邊。
            通過這一個性質(zhì),加上網(wǎng)絡(luò)N前后兩次的topo序列,我們不難發(fā)現(xiàn),結(jié)尾網(wǎng)絡(luò)topo序列的最后一個肯定是在操作中失去出度而從初始的topo序列降為(或停留)最后面,所以,將其可反轉(zhuǎn)的入度邊反向,肯定不會存在回射邊從而產(chǎn)生環(huán)結(jié)構(gòu),因此,從最后一個點向前搜索,每次執(zhí)行可執(zhí)行的反轉(zhuǎn)操作,那么一定能保持當(dāng)前點的不存在回射邊。
            對于一個點,可存在同時支配多條可反轉(zhuǎn)邊,因為答案要求一次一次執(zhí)行反轉(zhuǎn),如果對于同一個點順序不當(dāng)可能出現(xiàn)環(huán),所以我們考慮以下問題:x->y, x->z,如果反轉(zhuǎn)(x,y)從而導(dǎo)致了環(huán)的出現(xiàn),那么可以肯定z->y是成立的,而在topo關(guān)系上z比y靠前,所以我們對于同一個點輸出結(jié)果時,要按照其初始網(wǎng)絡(luò)的topo順序,從左向右輸出。
            思路完畢,AC,證明....略了吧,我證明了一草稿紙。
            注意不要用矩陣,我因為那個吃了幾次CE......
            代碼:
            #include <iostream>
            #include 
            <cstdio>
            #include 
            <cstring>
            #include 
            <queue>
            #include 
            <vector>
            #define N 1100
            #define M 10010
            using namespace std;

            int n, m;

            struct edge
            {
                
            int u, v, next;
            } et[
            2][M];

            int eh[2][N], tot[2];
            int be[2 * N], ed[2 * N], sta[2 * N];
            int deg[2][N], deg2[N];
            int g[N][N];

            void add(int u, int v, int i)
            {
                
            int t = ++tot[i];
                et[i][t].u 
            = u;
                et[i][t].v 
            = v;
                et[i][t].next 
            = eh[i][u];
                eh[i][u] 
            = t;
                deg[i][v]
            ++;
            }

            int topo(int eh[], edge et[], int que[], int deg[])
            {
                
            int i, j, k, top = -1, qt = 0;
                
            for (i = 1; i <= n; ++i)
                    deg2[i] 
            = deg[i];
                
            for (i = 1; i <= n; ++i)
                    
            if (deg2[i] == 0)
                        sta[
            ++top] = i;
                
            for (j = 1; j <= n; ++j)
                {
                    
            if (top == -1return 0;
                    
            int u = sta[top--];
                    que[qt
            ++= u;
                    
            for (i = eh[u]; i != -1; i = et[i].next)
                    {
                        deg2[et[i].v]
            --;
                        
            if (deg2[et[i].v] == 0) sta[++top] = et[i].v;
                    }
                }
                
            return 1;
            }

            int was[M], cnt;
            void slove()
            {
                
            int i, j, k;
                memset(was, 
            0sizeof(was));
                printf(
            "%d\n", cnt);
                
            for (i = n - 1; i >= 0--i)
                {
                    
            int u = ed[i];
                    
            for (j = 0; j < n; ++j)
                      
            if (g[u][be[j]] > 0)
                      {
                          
            if (was[g[u][be[j]]] == 0)
                          {
                              was[g[u][be[j]]] 
            = 1;
                              printf(
            "%d ", g[u][be[j]]);
                          }
                      }
                }
                
            if (cnt > 0) printf("\n");
            }

            int main()
            {
                
            int i, j, k;
                
            while (scanf("%d%d"&n, &m) != EOF)
                {
                    memset(eh, 
            -1sizeof(eh));
                    memset(deg, 
            0sizeof(deg));
                    
            for (i = 1; i <= n; ++i)
                      
            for (j = 1; j <= n; ++j)
                        g[i][j] 
            = 0;
                    tot[
            1= tot[0= 0;
                    cnt 
            = 0;
                    
            int flag = 1;
                    
            for (i = 1; i <= m; ++i)
                    {
                        
            int a, b, c;
                        scanf(
            "%d%d%d"&a, &b, &c);
                        add(a, b, 
            0);
                        
            if (c)
                        {
                            add(b, a, 
            1);
                            cnt
            ++;
                            
            if (g[a][b] > 0) flag = 0;
                            g[a][b] 
            = i;
                        }
                        
            else
                          add(a, b, 
            1);
                    }
                    
            if (flag == 0)
                    {
                        printf(
            "-1\n\n");
                        
            continue;
                    }
                    
            int first = topo(eh[0], et[0], be, deg[0]);
                    
            int last = topo(eh[1], et[1], ed, deg[1]);
                    
            if (!(first && last))
                    {
                        printf(
            "-1\n\n");
                        
            continue;
                    }
                    slove();
                    printf(
            "\n");
                }
                
            return 0;
            }
            posted on 2011-10-15 22:12 LLawliet 閱讀(150) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            99久久亚洲综合精品网站| 国产成人99久久亚洲综合精品 | 久久99国产亚洲高清观看首页| 国产69精品久久久久久人妻精品| 欧美伊香蕉久久综合类网站| 色综合久久天天综合| 国产成年无码久久久久毛片| 久久精品水蜜桃av综合天堂| 天天躁日日躁狠狠久久 | 亚洲第一永久AV网站久久精品男人的天堂AV | 93精91精品国产综合久久香蕉| 久久91精品国产91久久小草| 久久夜色精品国产噜噜亚洲AV| 国产一区二区三区久久| 国产精品免费看久久久| 久久ww精品w免费人成| 国产99精品久久| 香蕉久久永久视频| 久久人人添人人爽添人人片牛牛| 久久精品无码午夜福利理论片| 久久久久人妻一区精品色| 国产精品99久久免费观看| 国产成人精品久久一区二区三区 | 国产高潮国产高潮久久久| 久久久精品一区二区三区| 久久国产精品二国产精品| 婷婷久久久亚洲欧洲日产国码AV| 国产三级久久久精品麻豆三级| 中文字幕亚洲综合久久2| 久久免费视频一区| 狠狠色噜噜狠狠狠狠狠色综合久久| 久久久久四虎国产精品| 久久久久久国产a免费观看黄色大片| 日本欧美久久久久免费播放网| A狠狠久久蜜臀婷色中文网| 久久艹国产| 欧美va久久久噜噜噜久久| 久久精品成人欧美大片| 国产精品一久久香蕉产线看 | 免费一级欧美大片久久网| 日产精品久久久久久久|