某島

… : "…アッカリ~ン . .. . " .. .
August 22, 2010

POJ 3469. Dual Core CPU

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