최대 권 폐쇄 도 hdu 3879 Base Station 템 플 릿 이 있 습 니 다!

Description
새로운 기술 이 휴대 전화 통신 시장 에 충격 을 주 고 있 는데 각 통신사 들 에 게 이것 은 기회 이자 도전 이다.THU 그룹 계열 의 CS & amp; T 통신 은 차세 대 통신 기술 혈전 의 전야 에 너무 많은 준비 작업 을 해 야 하 며, 사이트 하나만 선택 하면 전기 시장 연구, 사이트 측량, 최적화 등 프로젝트 를 완성 해 야 한다.초기 에 시장 조사 와 사이트 측량 을 한 후에 회 사 는 모두 N 개의 통신 신호 로 환 승 할 수 있 는 주 소 를 얻 었 다. 이런 주소 의 지리 적 위치 차이 로 인해 서로 다른 곳 에서 통신 환 승 소 를 건설 하 는 데 투입 해 야 하 는 비용 도 다르다. 다행히 전기 조사 후에 이런 것들 은 모두 이미 알 고 있 는 데이터 이다. i 번 째 통신 환 승 소 를 설립 하 는 데 필요 한 비용 은 Pi 이다.(1 ≤ i ≤ N). 또한 회 사 는 모든 기대 하 는 사용자 군 을 조사 하여 총 M 개 를 얻 었 습 니 다. i 번 째 사용자 군 에 대한 정 보 는 Ai, Bi 와 Ci 로 요약 합 니 다. 이 사용자 들 은 중계 역 Ai 와 중계 역 Bi 를 사용 하여 통신 을 하고 회 사 는 이익 을 얻 을 수 있 습 니 다. (1 ≤ i ≤ M, 1 ≤ Ai, Bi ≤ N) THU 그룹의 CS & T 회 사 는 선택 적 으로 일부 중계 역 (투입 원가) 을 설립 할 수 있 습 니 다.일부 사용자 에 게 서 비 스 를 제공 하고 수익 (수익 의 합) 을 얻 습 니 다. 그러면 최종 적 으로 설립 된 중계 역 을 어떻게 선택해 야 회사 의 순이익 이 가장 클 수 있 습 니까? (순이익 = 수익 의 합 - 투입 원가 의 합)
Input
입력 파일 의 첫 번 째 줄 에는 두 개의 정수 N 과 M 이 있 습 니 다. 두 번 째 줄 에는 N 개의 정수 가 있 습 니 다. 각 통신 중계 국 의 구축 원 가 를 설명 합 니 다. P1, P2,..., PN 순 입 니 다. 아래 M 줄, 두 번 째 줄 의 세 번 째 숫자 Ai, Bi 와 Ci 는 두 번 째 사용자 군의 정 보 를 설명 합 니 다. 모든 변 량 의 의 미 는 제목 설명 을 참조 할 수 있 습 니 다.
Output
프로그램 이 출력 파일 에 정 수 를 출력 하기 만 하면 회사 가 얻 을 수 있 는 최대 순이익 을 표시 합 니 다.
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

Hint
안 만들어 주 는 템 플 릿 이 뭐 가 틀 렸 어 요 orz 그리고 이 원 제 는 NOI 의........................................................................

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100000;
const int maxe=1000000;
int sum,s,e,head[maxn],level[maxn],que[maxn];
struct node{
     int w,to,next;
}edge[maxe];
void add(int u,int v,int c)
{
    edge[sum].to=v;
    edge[sum].w=c;
    edge[sum].next=head[u];
    head[u]=sum++;
    edge[sum].to=u;
    edge[sum].w=0;
    edge[sum].next=head[v];
    head[v]=sum++;
}
bool bfs()
{
    memset(level,0,sizeof(level));
    int p=0;
    que[p++]=s;
    level[s]=1;
    for(int i=0;i<p;i++)
    {
        int temp=que[i];
        for(int k=head[temp];k>-1;k=edge[k].next)
        if(edge[k].w && (!level[edge[k].to])){
            que[p++]=edge[k].to;
            level[edge[k].to]=level[temp]+1;
        }
    }
    return level[e];
}
 
int dfs(int now,int maxf)
{
    if(now==e)return maxf;
    int ret=0;
    for(int i=head[now];i>-1 && ret<maxf; i=edge[i].next)
    if(edge[i].w && (level[edge[i].to]==level[now]+1))
    {
        int temp=dfs(edge[i].to,min(maxf-ret,edge[i].w));
        edge[i].w-=temp;
        edge[i^1].w+=temp;
        ret+=temp;
    }
    if(ret==0)level[now]=0;
    return ret;
}
 
int dinic()
{
    int ans=0;
    while(bfs())ans+=dfs(s,inf);
    return ans;
}
 
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m,x;
    while(~scanf("%d%d",&n,&m)){
        sum=0;
        memset(head,-1,sizeof(head));
        s=0,e=n+m+1;
        for(int i=1;i<=n;i++){
        scanf("%d",&x);
        add(i+m,e,x);
        }
        int count=0;
        for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(i,a+m,inf);
        add(i,b+m,inf);
        add(s,i,c);
        count+=c;
        }
        //cout<<dinic()<<endl;
        printf("%d
",count-dinic());
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100000;
const int maxe=1000000;
int sum,s,e,head[maxn],level[maxn],que[maxn];
struct node{
     int w,to,next;
}edge[maxe];
void add(int u,int v,int c)
{
    edge[sum].to=v;
    edge[sum].w=c;
    edge[sum].next=head[u];
    head[u]=sum++;
    edge[sum].to=u;
    edge[sum].w=0;
    edge[sum].next=head[v];
    head[v]=sum++;
}
bool bfs()
{
    memset(level,0,sizeof(level));
    int p=0;
    que[p++]=s;
    level[s]=1;
    for(int i=0;i<p;i++)
    {
        int temp=que[i];
        for(int k=head[temp];k>-1;k=edge[k].next)
        if(edge[k].w && (!level[edge[k].to])){
            que[p++]=edge[k].to;
            level[edge[k].to]=level[temp]+1;
        }
    }
    return level[e];
}
 
int dfs(int now,int maxf)
{
    if(now==e)return maxf;
    int ret=0;
    for(int i=head[now];i>-1 && ret<maxf; i=edge[i].next)
    if(edge[i].w && (level[edge[i].to]==level[now]+1))
    {
        int temp=dfs(edge[i].to,min(maxf-ret,edge[i].w));
        edge[i].w-=temp;
        edge[i^1].w+=temp;
        ret+=temp;
    }
    if(ret==0)level[now]=0;
    return ret;
}
 
inline int dinic()
{
    int ans=0;
    while(bfs())ans+=dfs(s,inf);
    return ans;
}
 
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m,x;
    while(~scanf("%d%d",&n,&m)){
        sum=0;
        memset(head,-1,sizeof(head));
        s=0,e=n+m+1;
        for(int i=1;i<=n;i++){
        scanf("%d",&x);
        add(i+m,e,x);
        }
        int count=0;
        for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(i,a+m,inf);
        add(i,b+m,inf);
        add(s,i,c);
        count+=c;
        }
        //cout<<dinic()<<endl;
        printf("%d
",count-dinic());
    }
    return 0;
}