Brief description :

给定 n 个进程在两个不同的核心上运行的代价ai, bi，一些进程之间可能存在联系，给定 m 个这样的三元组 (xi, yi, ci)，如果 xi, yi 不能在同一个核心上运行则会产生额外的 ci 份转移代价，求最小。

Analyse :

我写一些别的吧。。。感觉这些应用最小割求解的题。。我总是喜欢硬从最大流的方向开始思考。。结果往往是想了好多时间。。伤害了好多脑细胞。

还有，设定常量的时候，我总是喜欢算的很仔细，让空间一份也不多，之前一直 Runtime Error，怎么改都不对，一怒之下看了人家的标程，发现他把 M 设定成 50W，于是我也设定成 50 W，AC … （7000ms+）

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 20001, M =  500000;
struct edge{
    int v, c;
    void insert(int, int);
};

struct node{
    vector adj;
    int D;
};

struct network_flow{
    node V[N+1]; edge E[M+1];
    int edge_count, max_flow;
    int n, m, s, t;
    void init();
    void add_edge(int, int, int);
    void bfs();
    void Dinitz();
};

inline int _r(int x){
    return x ^ 1;
}


void edge::insert(int a, int b){
    v = a; c = b;
};

void network_flow::add_edge(int x, int y, int c){
    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, c);
}

void network_flow::bfs(){
    int Q[N+1] = {s}, head = 0, tail = 1;
    for (int i=1;i<=n;i++) V[i].D = -1; //memset(V.D, -1, sizeof(V.D));
    V[s].D = 0;

    int u;
    while (head
External link :
http://acm.pku.edu.cn/JudgeOnline/problem?id=3469

http://www.answeror.com/archives/27504

http://hi.baidu.com/gugugupan/blog/item/04f2e81aa6a969fdaf513381.html
                                                												

													Posted by 
													xiaodao													
													Category: 													日常