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

            Base Station

            Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 65768/32768 K (Java/Others)
            Total Submission(s): 844    Accepted Submission(s): 353


            Problem Description
            A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is Pi (1<=i<=n).

            When complete building, two places which both have stations can communicate with each other.

            Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers Ai, Bi and Ci, which means if place Aand Bi can communicate with each other, the company will get Ci profit.

            Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.
             

            Input
            Multiple test cases (no more than 20), for each test case:
            The first line has two integers n (0<n<=5000) and m (0<m<=50000).
            The second line has n integers, P1 through Pn, describes the cost of each location.
            Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.
             

            Output
            One integer each case, the maximum profit of the company.
             

            Sample Input
            5 5 1 2 3 4 5 1 2 3 2 3 4 1 3 3 1 4 2 4 5 3
             

            Sample Output
            4
             

            Author
            liulibo
             

            Source
             

            Recommend
            lcy
             
            論文題,Amber最小割模型里面的,最大權閉合圖,因為數組開的太大了,吃了一次RE......
            最大權閉合圖不用說了,邊看成收益點,連向S,流量是點權,站點看成花費點,連向T,流量也是點權,其他按照原圖連邊,流量是無限大,之后做一次最小割,割值就是你未選的收益點+選定花費點(因為是閉合圖,所以割肯定是簡單割,想一下割的定義,就明白割值的含義了),用你總收益-割值,就是答案。
            用SAP求的最小割,漸漸愛上SAP了,Dinic不用了.....
            代碼:

            #include <cstdio>
            #include 
            <cstring>
            #include 
            <iostream>
            #include 
            <queue>
            using namespace std;

            const int maxnode = 60000;
            const int maxedge = 320000;
            const long long inf = (1LL << 35);

            int S, T, cnt;
            int head[maxnode], gap[maxnode], pre[maxnode], cur[maxnode], dis[maxnode];

            struct Edge
            {
                
            int s, t;
                
            int next;
                
            long long w;
            } st[maxedge];

            void init()
            {
                memset(head, 
            -1sizeof(head));
                cnt 
            = 0;
            }

            void AddEdge(int s, int t, long long w)
            {
                st[cnt].s 
            = s;
                st[cnt].t 
            = t;
                st[cnt].w 
            = w;
                st[cnt].next 
            = head[s];
                head[s] 
            = cnt;
                cnt
            ++;

                st[cnt].s 
            = t;
                st[cnt].t 
            = s;
                st[cnt].w 
            = 0;
                st[cnt].next 
            = head[t];
                head[t] 
            = cnt;
                cnt
            ++;
            }

            void bfs()
            {
                memset(gap, 
            0sizeof(gap));
                memset(dis, 
            -1sizeof(dis));
                queue 
            <int> Q;
                Q.push(T);
                dis[T] 
            = 0;
                gap[
            0= 1;
                
            int k, t;
                
            while (!Q.empty())
                {
                    k 
            = Q.front();
                    Q.pop();
                    
            for (int i = head[k]; i != -1; i =st[i].next)
                    {
                        t 
            = st[i].t;
                        
            if (dis[t] == -1 && st[i ^ 1].w > 0)
                        {
                            dis[t] 
            = dis[k] + 1;
                            gap[dis[t]]
            ++;
                            Q.push(t);
                        }
                    }
                }
            }

            long long sap()
            {
                
            int i;
                
            for (i = S; i <= T; ++i)
                    cur[i] 
            = head[i];
                pre[S] 
            = S;
                
            int u = S, v;
                
            long long flow = 0;
                
            long long aug = inf;
                
            bool flag;
                
            while (dis[S] <= T)
                {
                    flag 
            = false;
                    
            for (i = cur[u]; i != -1; i = st[i].next)
                    {
                        v 
            = st[i].t;
                        
            if (st[i].w > 0 && dis[u] == dis[v] + 1)
                        {
                            cur[u] 
            = i;
                            flag 
            = true;
                            pre[v] 
            = u;
                            aug 
            = (aug > st[i].w) ? st[i].w : aug;
                            u 
            = v;
                            
            if (v == T)
                            {
                                flow 
            += aug;
                                
            for (u = pre[u]; v != S; u = pre[u])
                                {
                                    v 
            = u;
                                    st[cur[u]].w 
            -= aug;
                                    st[cur[u] 
            ^ 1].w += aug;
                                }
                                aug 
            = inf;
                            }
                            
            break;
                        }
                    }
                    
            if (flag == truecontinue;
                    
            int mint = T;
                    
            for (i = head[u]; i != -1; i = st[i].next)
                    {
                        v 
            = st[i].t;
                        
            if (st[i].w > 0 && mint > dis[v])
                        {
                            cur[u] 
            = i;
                            mint 
            = dis[v];
                        }
                    }
                    gap[dis[u]]
            --;
                    
            if (gap[dis[u]] == 0break;
                    gap[dis[u] 
            = mint + 1]++;
                    u 
            = pre[u];
                    
            if (u == S) aug = inf;
                }
                
            return flow;
            }

            int main()
            {
                
            int n, m;
                
            while (scanf("%d%d"&n, &m) != EOF)
                {
                    init();
                    S 
            = 0;
                    T 
            = n + m + 1;
                    
            int sum = 0;
                    
            for (int i = 1; i <= n; ++i)
                    {
                        
            int x;
                        scanf(
            "%d"&x);
                        AddEdge(m 
            + i, T, x);
                    }
                    
            for (int i = 1; i <= m; ++i)
                    {
                        
            int a, b, c;
                        scanf(
            "%d%d%d"&a, &b, &c);
                        AddEdge(S, i, c);
                        AddEdge(i, m 
            + a, inf);
                        AddEdge(i, m 
            + b, inf);
                        sum 
            += c;
                    }
                    bfs();
                    sum 
            -= sap();
                    printf(
            "%d\n", sum);
                }
                
            return 0;
            }
            posted on 2011-10-15 22:10 LLawliet 閱讀(126) 評論(0)  編輯 收藏 引用 所屬分類: 網絡流
            66精品综合久久久久久久| 国产精品久久久亚洲| 思思久久好好热精品国产| 久久99久久99精品免视看动漫| 无码AV中文字幕久久专区| 久久久久久久综合日本| 久久久久久亚洲精品成人| 午夜福利91久久福利| 久久91精品综合国产首页| 久久免费高清视频| 久久国产亚洲精品麻豆| 亚洲AV日韩精品久久久久久久| 99久久99久久| 青青草原1769久久免费播放| 亚洲精品综合久久| 一级女性全黄久久生活片免费| 久久精品麻豆日日躁夜夜躁| 一本久久综合亚洲鲁鲁五月天| 99久久人妻无码精品系列蜜桃 | 久久无码AV一区二区三区| 亚洲国产精品久久久天堂 | 欧美大香线蕉线伊人久久| av色综合久久天堂av色综合在| 久久人做人爽一区二区三区 | 色婷婷狠狠久久综合五月| 97久久精品人人澡人人爽| 国内精品九九久久精品| 久久一区二区三区99| 国产高潮国产高潮久久久91 | 色综合久久综精品| 久久超乳爆乳中文字幕| 99精品久久久久久久婷婷| 久久国产高清一区二区三区| 欧美精品一区二区精品久久| 精品熟女少妇a∨免费久久| 欧美午夜精品久久久久免费视 | 亚洲国产精品人久久| 国产激情久久久久影院老熟女免费 | 色狠狠久久综合网| 久久毛片一区二区| 久久www免费人成看片|