• <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最小割模型里面的,最大權(quán)閉合圖,因?yàn)閿?shù)組開(kāi)的太大了,吃了一次RE......
            最大權(quán)閉合圖不用說(shuō)了,邊看成收益點(diǎn),連向S,流量是點(diǎn)權(quán),站點(diǎn)看成花費(fèi)點(diǎn),連向T,流量也是點(diǎn)權(quán),其他按照原圖連邊,流量是無(wú)限大,之后做一次最小割,割值就是你未選的收益點(diǎn)+選定花費(fèi)點(diǎn)(因?yàn)槭情]合圖,所以割肯定是簡(jiǎn)單割,想一下割的定義,就明白割值的含義了),用你總收益-割值,就是答案。
            用SAP求的最小割,漸漸愛(ài)上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 閱讀(130) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 網(wǎng)絡(luò)流
            国产麻豆精品久久一二三| 欧美精品久久久久久久自慰| 亚洲中文字幕无码久久综合网| 久久99精品久久久久久齐齐| 久久久久久无码国产精品中文字幕| 亚洲?V乱码久久精品蜜桃| 乱亲女H秽乱长久久久| 99国产精品久久| 免费一级欧美大片久久网| 少妇精品久久久一区二区三区 | 亚洲av成人无码久久精品| 色综合久久综合中文综合网| 一级a性色生活片久久无| 99热成人精品热久久669| 91精品国产高清久久久久久国产嫩草| 久久亚洲AV永久无码精品| 无夜精品久久久久久| 99久久99这里只有免费费精品 | 久久精品国产99国产精品导航| 国产精品久久国产精品99盘| 婷婷久久综合| 91精品国产高清久久久久久91| 亚洲国产精品久久电影欧美| 久久福利片| 夜夜亚洲天天久久| 久久精品亚洲精品国产色婷| 少妇内射兰兰久久| 亚洲欧洲久久av| 久久激情亚洲精品无码?V| 久久精品国产免费| 91精品国产91热久久久久福利 | 久久综合偷偷噜噜噜色| 精品久久久久久久久久久久久久久 | 久久综合狠狠综合久久| 亚洲精品国精品久久99热| 久久久久亚洲AV成人网| 国产精品热久久无码av| 亚洲国产香蕉人人爽成AV片久久| 色综合合久久天天综合绕视看| 日本精品久久久久中文字幕8| 精品久久香蕉国产线看观看亚洲|