Tag:网络流
Article From:https://www.cnblogs.com/Khada-Jhin/p/9123359.html

Title Description

The new technology is affecting the mobile phone communication market. For the major operators, this is both an opportunity and a challenge. THU group’s CS& T communications company needs to do too much preparation on the eve of the new generation of communications technology bloodbattle. Only one site selection will require the completion of the early market research.Research, site survey, optimization and other projects. After the previous market survey and site survey, the company received a total of N addresses that can be used as a communication signal transfer station, and because of the geographical location differences of these addresses, the cost of building a communication transit station in different places is also different, fortunately in the previous period.After investigation, these are known data: the cost of establishing the I communication transfer station is Pi (1 I or less than N). In addition, the company surveyed all the expected user groups, a total of M. Information about the I user group is summarized as Ai, Bi and Ci: these users will use the transit station Ai andThe transfer station Bi communicates, and the company can benefit from Ci. (1 < I < < < M, 1 < Ai, Bi < N) THU group CS& T company can choose to establish some transfer stations (input cost), provide service for some users and gain profit (benefit sum). So howCan we choose the final transfer station to maximize the net profit of the company? (net profit = sum of benefits - the sum of input costs)

input

The first line in the input file has two positive integers N and M. There are N integers in the second row to describe the establishment cost of each communication transfer station, followed by P1, P2,… PN. The following M lines, the three numbers of (I + 2) row Ai, Bi and Ci describe the information of the I user group.. The meaning of all variables can be described in the title description.

output

As long as your program outputs an integer to the output file, it shows the maximum net profit that the company can get.

 

This problem is the introduction of the maximum weight closure subgraph. The source point is connected to the user group, the capacity is revenue; the transfer station connects to the sink point, and the capacity is cost. Each user group is connected to the corresponding transfer station with a capacity of INF. The minimum cut (maximum flow) of the network is obtained, and the minimum cut can be reduced by total revenue.

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<cstring>
  6 using namespace std;
  7 int head[60001];
  8 int to[400001];
  9 int val[400001];
 10 int next[400001];
 11 int tot=1;
 12 int n,m;
 13 int x;
 14 int a,b,c;
 15 int S,T;
 16 int d[60001];
 17 int q[60001];
 18 int INF=2147483647;
 19 int ans=0;
 20 int sum=0;
 21 void add(int x,int y,int z)
 22 {
 23     tot++;
 24     next[tot]=head[x];
 25     head[x]=tot;
 26     to[tot]=y;
 27     val[tot]=z;
 28     tot++;
 29     next[tot]=head[y];
 30     head[y]=tot;
 31     to[tot]=x;
 32     val[tot]=0;
 33 }
 34 int dfs(int x,int maxflow)
 35 {
 36     if(x==T)
 37     {
 38         return maxflow;
 39     }
 40     int used=0;
 41     int nowflow;
 42     for(int i=head[x];i;i=next[i])
 43     {
 44         if(val[i]!=0&&d[to[i]]==d[x]+1)
 45         {
 46             nowflow=dfs(to[i],min(maxflow-used,val[i]));
 47             val[i]-=nowflow;
 48             val[i^1]+=nowflow;
 49             used+=nowflow;
 50             if(nowflow==maxflow)
 51             {
 52                 return maxflow;
 53             }
 54         }
 55     }
 56     if(used==0)
 57     {
 58         d[x]=-1;
 59     }
 60     return used;
 61 }
 62 bool bfs(int S,int T)
 63 {
 64     memset(d,-1,sizeof(d));
 65     memset(q,0,sizeof(q));
 66     d[S]=0;
 67     int l=0;
 68     int r=0;
 69     q[r++]=S;
 70     while(l<r)
 71     {
 72         int now=q[l];
 73         for(int i=head[now];i;i=next[i])
 74         {
 75             if(d[to[i]]==-1&&val[i]!=0)
 76             {
 77                 d[to[i]]=d[now]+1;
 78                 q[r++]=to[i];
 79             }
 80         }
 81         l++;
 82     }
 83     if(d[T]!=-1)
 84     {
 85         return true;
 86     }
 87     return false;
 88 }
 89 void dinic()
 90 {
 91     while(bfs(S,T)==true)
 92     {
 93         ans+=dfs(S,INF);
 94     }
 95 }
 96 int main()
 97 {
 98     scanf("%d%d",&n,&m);
 99     S=n+m+1;
100     T=n+m+2;
101     for(int i=1;i<=n;i++)
102     {
103         scanf("%d",&x);
104         add(i+m,T,x);
105     }
106     for(int i=1;i<=m;i++)
107     {
108         scanf("%d%d%d",&a,&b,&c);
109         sum+=c;
110         add(S,i,c);
111         add(i,a+m,INF);
112         add(i,b+m,INF);
113     }
114     dinic();
115     printf("%d",sum-ans);
116 }

 

Leave a Reply

Your email address will not be published. Required fields are marked *