二次聯通門 :?codevs 1422 河城荷取
?
?
?
?
/*codevs 1422 河城荷取二分費用重新構圖最大流判斷是否可行用了鄰接矩陣來存初始的流量和費用。。。慢的要死*/ #include <cstring> #include <cstdio> #include <queue>#define Max 2003 #define INF 1e9void read (int &now) {register char word = getchar ();for (now = 0; word < '0' || word > '9'; word = getchar ());for (; word >= '0' && word <= '9'; now = now * 10 + word - '0', word = getchar ()); }int N, M, L, K;int can_flow[Max][Max]; int cost[Max][Max];inline int max (int &a, int &b) {return a > b ? a : b; }inline int min (int &a, int &b) {return a < b ? a : b; } int T; const int S = 0;class Net_Flow_Type {private :int __to[Max * Max], __next[Max * Max];int __flow[Max * Max];int Edge_Count;int edge_list[Max];int deep[Max];int __tech_[Max];public :inline void Clear (){Edge_Count = 1;memset (edge_list, 0, sizeof edge_list);}inline void Insert_edge (int from, int to, int key){Edge_Count ++;__to[Edge_Count] = to;__next[Edge_Count] = edge_list[from];edge_list[from] = Edge_Count;__flow[Edge_Count] = key;Edge_Count ++;__to[Edge_Count] = from;__next[Edge_Count] = edge_list[to];edge_list[to] = Edge_Count;__flow[Edge_Count] = 0;}bool Bfs (){std :: queue <int> Queue;memset (deep, -1, sizeof deep);deep[S] = 0;register int now;for (Queue.push (S); !Queue.empty (); Queue.pop ()){now = Queue.front ();register int i;for (i = edge_list[now]; i; i = __next[i])if (deep[__to[i]] < 0 && __flow[i]){deep[__to[i]] = deep[now] + 1;if (__to[i] == T)return true;Queue.push (__to[i]); }}return deep[T] != -1;}int Flowing (int now, int flow){if (now == T || flow == 0)return flow;int res, last = 0;for (int &i = __tech_[now]; i; i = __next[i]){if (deep[__to[i]] != deep[now] + 1 || __flow[i] == 0)continue;res = Flowing (__to[i], min (flow, __flow[i]));if (res > 0){last += res;flow -= res;__flow[i] -= res;__flow[i ^ 1] += res;if (flow == 0)return last;}}if (flow != last)deep[now] = -1;return last;}int Dinic (){int Answer = 0;while (Bfs ()){memcpy ( __tech_,edge_list, sizeof edge_list);Answer += Flowing (S, INF);}return Answer;} };Net_Flow_Type Flow;bool Judge (int key) {Flow.Clear ();for (register int i = 1; i <= L; i ++)Flow.Insert_edge (S, i, INF);for (register int i = 1, j; i <= N; i ++)for (j = 1; j <= N; j ++){if (i == j)continue;if (cost[i][j] <= key)Flow.Insert_edge (i, j, can_flow[i][j]);}Flow.Insert_edge (N, T, INF);return Flow.Dinic () >= K; }int Answer;int main (int argc, char *argv[]) {read (N);read (M);read (L);read (K);T = N + 1;int l = 0, r = -INF, Mid;memset (cost, 0x3f, sizeof cost);int x, y, z, s;for (register int i = 1; i <= M; i ++){read (x);read (y);read (z);read (s);can_flow[x][y] = z;cost[x][y] = s;r = max (r, s);}for (; l <= r; ){Mid = l + r >> 1;if (Judge (Mid)){r = Mid - 1;Answer = Mid;}elsel = Mid + 1;}printf ("%d", Answer);return 0; }
?
