• <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)  編輯 收藏 引用 所屬分類: 網絡流
            久久精品成人免费网站| 国产69精品久久久久99| 区久久AAA片69亚洲| 亚洲国产精品无码久久| 狠狠色丁香婷婷久久综合不卡| 国产精品丝袜久久久久久不卡 | 久久久久久久91精品免费观看| 久久无码精品一区二区三区| 久久人人爽人人爽人人AV东京热| 99热精品久久只有精品| 综合人妻久久一区二区精品| 国产毛片久久久久久国产毛片 | 久久国产成人午夜aⅴ影院| 囯产极品美女高潮无套久久久 | 伊人久久大香线蕉精品| 久久午夜夜伦鲁鲁片免费无码影视| 久久国产精品一国产精品金尊 | 91秦先生久久久久久久| 色欲av伊人久久大香线蕉影院| 久久国产影院| www亚洲欲色成人久久精品| 久久精品国产亚洲AV无码偷窥| 色狠狠久久综合网| 亚洲国产成人精品无码久久久久久综合 | 午夜视频久久久久一区| 国内精品久久久久影院网站| 久久综合久久综合九色| 国产精品一区二区久久不卡| 精品久久久无码21p发布| 一本色道久久综合狠狠躁篇| 久久99久久成人免费播放| 免费精品99久久国产综合精品| 国产精品美女久久久m| 久久婷婷五月综合色高清| 日韩精品久久无码人妻中文字幕 | 久久综合精品国产二区无码| 亚洲成色www久久网站夜月| 久久婷婷五月综合色奶水99啪| 日韩人妻无码一区二区三区久久| 人妻丰满AV无码久久不卡| 久久发布国产伦子伦精品|