首页 > 代码库 > POJ3469_Dual Core CPU(网络流/最小割=最大流/模版)----Dinic模版2.0

POJ3469_Dual Core CPU(网络流/最小割=最大流/模版)----Dinic模版2.0

2024-07-18 05:53:39   225人阅读

解题报告

题目传送门

题意：

双核CPU，n个模块，每个模块必须运行在某个CPU核心上，每个模块在cpu单核的消耗A和B，M对模块要共享数据，如果在同一个核心上不用消耗，否则需要耗费。安排N个模块，使得总耗费最小

思路：

将两个cpu核心看成源点和汇点，其他模块分别与源点汇点连线（表示每个模块可以在任意cpu上运行），m对模块分别连双向边，要使得模块只能在一个cpu上运行，就是找到一个割，源点和汇点必不联通，耗费最少就是最小割，最小割最大流原理转换成求最大流。

这题数据大，没优化TLE了，加了两优化就过了。

更新模版

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define M 6050000
#define N 320000
#define inf 0x3f3f3f3f
using namespace std;
struct node {
    int v,w,next;
} edge[M];
int head[N],cnt,l[N],n,m,s,t;
void add(int u,int v,int w) {
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].w=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void add2(int u,int v,int w) {
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].w=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
int bfs() {
    memset(l,-1,sizeof(l));
    l[s]=0;
    int i,u,v;
    queue<int >Q;
    Q.push(s);
    while(!Q.empty()) {
        u=Q.front();
        Q.pop();
        for(i=head[u]; i!=-1; i=edge[i].next) {
            v=edge[i].v;
            if(l[v]==-1&&edge[i].w) {
                l[v]=l[u]+1;
                Q.push(v);
            }
        }
    }
    return l[t]>0;
}
int dfs(int u,int f) {
    int a,flow=0;
    if(u==t)return f;
    for(int i=head[u]; i!=-1; i=edge[i].next) {
        int v=edge[i].v;
        if(l[v]==l[u]+1&&edge[i].w&&(a=dfs(v,min(f,edge[i].w)))) {
            edge[i].w-=a;
            edge[i^1].w+=a;
            flow+=a;//多路增广
            f-=a;
            if(!f)break;
        }
    }
    if(!flow)l[u]=-1;//当前弧优化
    return flow;
}
int dinic() {
    int a,ans=0;
    while(bfs())
        while(a=dfs(s,inf))
            ans+=a;
    return ans;
}
int main() {
    int i,j,u,v,w;
    while(~scanf("%d%d",&n,&m)) {
        memset(head,-1,sizeof(head));
        cnt=0;
        s=0;
        t=n+1;
        for(i=1; i<=n; i++) {
            scanf("%d%d",&u,&v);
            add(s,i,u);
            add(i,t,v);
        }
        for(i=1; i<=m; i++) {
            scanf("%d%d%d",&u,&v,&w);
            add2(u,v,w);
        }
        printf("%d\n",dinic());
    }
}

Dual Core CPU
Time Limit: 15000MS Memory Limit: 131072K
Total Submissions: 18883 Accepted: 8144
Case Time Limit: 5000MS

Description

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.

The routine consists of N modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let‘s define them as Ai and Bi. Meanwhile, Mpairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.

Input

There are two integers in the first line of input data, N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) .
The next N lines, each contains two integer, Ai and Bi.
In the following M lines, each contains three integers: a, b, w. The meaning is that if module a and module b don‘t execute on the same core, you should pay extra w dollars for the data-exchange between them.

Output

Output only one integer, the minimum total cost.

Sample Input

3 1
1 10
2 10
10 3
2 3 1000

Sample Output

13

Source

POJ Monthly--2007.11.25, Zhou Dong


联系
我们