• <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>

            USACO 4.1 Fence Loops


            ???? 這題是求無向圖中的一個最小環(huán)的長度。
            ???? 主要思路是:因為邊都是直線,邊的兩點之間的最短距離必然是這個邊長。那么,再求一條到兩頂點的最短距徑,這個路徑與邊構成了一個環(huán)。這個環(huán)是包含該邊的最小環(huán)。枚舉一下所有邊,計算出最小環(huán)即可。對于每個邊,刪除該邊,然后計算兩頂點的最短路徑,再恢復該邊。
            ???? 但是這個圖的輸入是用邊表示的,一個難點就是將其轉換成用點表示。這里用邊的集合來表示一個點。然后用map<set<int>,int>來存儲某一邊對應的邊的編號。每找到一個新的頂點則分配一個新的編號。這部分主要通過函數(shù)get_vertex(set<int>&s)來實現(xiàn)。

            代碼如下:
            #include?<iostream>
            #include?
            <fstream>
            #include?
            <set>
            #include?
            <map>
            #include?
            <climits>
            #include?
            <cstring>

            using?namespace?std;

            ifstream?fin(
            "fence6.in");
            ofstream?fout(
            "fence6.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            struct?Edge{
            ????
            int?va,vb,len;
            };

            int?edge_num;
            int?vertex_num;
            int?graph[100][100];
            Edge?edges[
            100];

            int?get_vertex(set<int>&s)
            {
            ????
            static?map<set<int>,int>vertex;

            ????
            if(?vertex.find(s)?==?vertex.end()?){
            ????????vertex[s]?
            =?vertex_num;
            ????????
            return?vertex_num++;
            ????}
            else{
            ????????
            return?vertex[s];
            ????}
            }

            void?build_graph()
            {
            ????
            in>>edge_num;

            ????
            for(int?i=0;i<100;++i)
            ????????
            for(int?j=0;j<100;++j)
            ????????????graph[i][j]?
            =?INT_MAX/2;

            ????
            for(int?i=0;i<edge_num;++i){
            ????????
            int?edge,tmp,len;
            ????????
            int?left_num,right_num;
            ????????
            set<int>?s;
            ????????
            in>>edge>>len>>left_num>>right_num;
            ????????s.insert(edge);
            ????????
            for(int?j=0;j<left_num;++j){
            ????????????
            in>>tmp;
            ????????????s.insert(tmp);
            ????????}
            ????????
            int?left_vertex?=?get_vertex(s);
            ????????s.clear();
            ????????s.insert(edge);
            ????????
            for(int?j=0;j<right_num;++j){
            ????????????
            in>>tmp;
            ????????????s.insert(tmp);
            ????????}
            ????????
            int?right_vertex?=?get_vertex(s);
            ????????graph[left_vertex][right_vertex]?
            =?
            ????????????graph[right_vertex][left_vertex]?
            =?len;
            ????????edges[i].va?
            =?left_vertex;
            ????????edges[i].vb?
            =?right_vertex;
            ????????edges[i].len?
            =?len;
            ????}
            }

            int?shortest_path(int?va,int?vb)
            {
            ????
            int?shortest[100];
            ????
            bool?visited[100];

            ????memset(visited,
            0,sizeof(visited));
            ???
            ????
            for(int?i=0;i<vertex_num;++i){
            ????????shortest[i]?
            =?graph[va][i];
            ????}

            ????visited[va]?
            =?true;

            ????
            while(true){
            ????????
            int?m?=?-1;
            ????????
            for(int?i=0;i<vertex_num;++i){
            ??????????????
            if(!visited[i]){
            ????????????????
            if(m==-1||shortest[i]<shortest[m])
            ????????????????????m?
            =?i;
            ??????????????}
            ????????}
            ????????
            //沒有新加結點了
            ????????
            ????????visited[m]?
            =?true;

            ????????
            if(?m==vb?)
            ????????????
            return?shortest[vb];

            ????????
            for(int?i=0;i<vertex_num;++i){
            ????????????
            if(!visited[i])
            ????????????shortest[i]?
            =?min(shortest[i],shortest[m]+graph[m][i]);
            ????????}
            ????}
            }

            void?solve()
            {
            ????build_graph();

            ????
            int?best?=?INT_MAX;

            ????
            for(int?i=0;i<edge_num;++i){
            ??????graph[edges[i].va][edges[i].vb]?
            =?graph[edges[i].vb][edges[i].va]?=?INT_MAX/2;?
            ??????best?
            =?min(best,edges[i].len+shortest_path(edges[i].va,edges[i].vb)?);
            ??????graph[edges[i].va][edges[i].vb]?
            =?graph[edges[i].vb][edges[i].va]?=?edges[i].len;?
            ????}

            ????
            out<<best<<endl;
            }

            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }


            Fence Loops

            The fences that surround Farmer Brown's collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only at their endpoints though sometimes more than two fences join together at a given endpoint. The result is a web of fences enclosing his pastures. Farmer Brown wants to start to straighten things out. In particular, he wants to know which of the pastures has the smallest perimeter.

            Farmer Brown has numbered his fence segments from 1 to N (N = the total number of segments). He knows the following about each fence segment:

            • the length of the segment
            • the segments which connect to it at one end
            • the segments which connect to it at the other end.
            Happily, no fence connects to itself.

            Given a list of fence segments that represents a set of surrounded pastures, write a program to compute the smallest perimeter of any pasture. As an example, consider a pasture arrangement, with fences numbered 1 to 10 that looks like this one (the numbers are fence ID numbers):

                       1
            +---------------+
            |\ /|
            2| \7 / |
            | \ / |
            +---+ / |6
            | 8 \ /10 |
            3| \9 / |
            | \ / |
            +-------+-------+
            4 5

            The pasture with the smallest perimeter is the one that is enclosed by fence segments 2, 7, and 8.

            PROGRAM NAME: fence6

            INPUT FORMAT

            Line 1: N (1 <= N <= 100)
            Line 2..3*N+1:

            N sets of three line records:

            • The first line of each record contains four integers: s, the segment number (1 <= s <= N); Ls, the length of the segment (1 <= Ls <= 255); N1s (1 <= N1s <= 8) the number of items on the subsequent line; and N2sthe number of items on the line after that (1 <= N2s <= 8).
            • The second line of the record contains N1 integers, each representing a connected line segment on one end of the fence.
            • The third line of the record contains N2 integers, each representing a connected line segment on the other end of the fence.

            SAMPLE INPUT (file fence6.in)

            10
            1 16 2 2
            2 7
            10 6
            2 3 2 2
            1 7
            8 3
            3 3 2 1
            8 2
            4
            4 8 1 3
            3
            9 10 5
            5 8 3 1
            9 10 4
            6
            6 6 1 2
            5
            1 10
            7 5 2 2
            1 2
            8 9
            8 4 2 2
            2 3
            7 9
            9 5 2 3
            7 8
            4 5 10
            10 10 2 3
            1 6
            4 9 5

            OUTPUT FORMAT

            The output file should contain a single line with a single integer that represents the shortest surrounded perimeter.

            SAMPLE OUTPUT (file fence6.out)

            12




            posted on 2009-07-17 14:26 YZY 閱讀(598) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO圖論

            導航

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            精品久久香蕉国产线看观看亚洲| 国产福利电影一区二区三区,免费久久久久久久精| 亚洲午夜久久久精品影院| 青青青国产精品国产精品久久久久| 88久久精品无码一区二区毛片 | 久久久久久国产精品美女| 久久久久久久久久久精品尤物 | 日本人妻丰满熟妇久久久久久| 99久久中文字幕| 久久综合久久综合亚洲| 久久久青草久久久青草| 99精品国产免费久久久久久下载| 久久久青草青青亚洲国产免观| 偷偷做久久久久网站| 久久精品国产99久久久香蕉| 午夜欧美精品久久久久久久| 麻豆久久| 久久国产综合精品五月天| 久久精品国产亚洲av高清漫画| 久久福利片| 亚洲欧美精品伊人久久| 99精品久久精品一区二区| 久久精品国产一区二区电影| 久久精品国产亚洲沈樵| 国产亚洲色婷婷久久99精品| 久久精品国产亚洲AV不卡| 伊人久久精品影院| 欧美久久综合九色综合| 91精品婷婷国产综合久久| 国产一区二区三区久久| 欧美综合天天夜夜久久| 亚洲国产精品久久| 久久国产乱子伦精品免费午夜| 亚洲嫩草影院久久精品| 国产AⅤ精品一区二区三区久久| 精品午夜久久福利大片| 亚洲一区中文字幕久久| 中文字幕久久欲求不满| 久久久噜噜噜久久中文字幕色伊伊| 国产高潮国产高潮久久久91 | 一本久久a久久精品综合夜夜 |