SHARE
TWEET

Untitled

_no0B Apr 25th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// Maximum Matching in General Graphs (Randomized Algorithm)
  2. #define MAX 1010
  3. bool adj[MAX][MAX];
  4. int n, ar[MAX][MAX];
  5. const int MOD = 1073750017;
  6. int expo(long long x, int n){
  7.     long long res = 1;
  8.  
  9.     while (n){
  10.         if (n & 1) res = (res * x) % MOD;
  11.         x = (x * x) % MOD;
  12.         n >>= 1;
  13.     }
  14.     return (res % MOD);
  15. }
  16. int rank(int n){ /// hash = 646599
  17.     long long inv;
  18.     int i, j, k, u, v, x, r = 0, T[MAX];
  19.     for (j = 0; j < n; j++){
  20.         for (k = r; k < n && !ar[k][j]; k++){}
  21.         if (k == n) continue;
  22.         inv = expo(ar[k][j], MOD - 2);
  23.         for (i = 0; i < n; i++){
  24.             x = ar[k][i];
  25.             ar[k][i] = ar[r][i];
  26.             ar[r][i] = (inv * x) % MOD;
  27.         }
  28.         for (u = r + 1; u < n; u++){
  29.             if (ar[u][j]){
  30.                 for (v = j + 1; v < n; v++){
  31.                     if (ar[r][v]){
  32.                         ar[u][v] = ar[u][v] - (((long long)ar[r][v] * ar[u][j]) % MOD);
  33.                         if (ar[u][v] < 0) ar[u][v] += MOD;
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.         r++;
  39.     }
  40.     return r;
  41. }
  42. int tutte(int n){
  43.     int i, j;
  44.     srand(time(0));
  45.     clr(ar);
  46.     for (i = 0; i < n; i++){
  47.         for (j = i + 1; j < n; j++){
  48.             if (adj[i][j]){
  49.                 unsigned int x = (rand() << 15) ^ rand();
  50.                 x = (x % (MOD - 1)) + 1;
  51.                 ar[i][j] = x, ar[j][i] = MOD - x;
  52.             }
  53.         }
  54.     }
  55.     return (rank(n) >> 1);
  56. }
  57. int main(){
  58.     int T = 0, t, m, i, j, a, b;
  59.     scanf("%d", &t);
  60.     while (t--){
  61.         clr(adj);
  62.         scanf("%d %d", &n, &m);
  63.         while (m--){
  64.             scanf("%d %d", &a, &b);
  65.             a--, b--;
  66.             adj[a][b] = adj[b][a] = true;
  67.         }
  68.         printf("Case %d: %d\n", ++T, tutte(n));
  69.     }
  70.     return 0;
  71. }
  72.  
  73.  
  74.  
  75. /// Min-cost Max-flow using SPFA (Shortest Path Faster Algorithm)
  76. /// 0 Based indexed for directed weighted graphs (for undirected graphs, just add two directed edges)
  77. namespace mcmf{
  78.     const int MAX = 1000010;
  79.     const long long INF = 1LL << 60;
  80.     long long cap[MAX], flow[MAX], cost[MAX], dis[MAX];
  81.     int n, m, s, t, Q[10000010], adj[MAX], link[MAX], last[MAX], from[MAX], visited[MAX];
  82.  
  83.     void init(int nodes, int source, int sink){
  84.         m = 0, n = nodes, s = source, t = sink;
  85.         for (int i = 0; i <= n; i++) last[i] = -1;
  86.     }
  87.     void addEdge(int u, int v, long long c, long long w){
  88.         adj[m] = v, cap[m] = c, flow[m] = 0, cost[m] = +w, link[m] = last[u], last[u] = m++;
  89.         adj[m] = u, cap[m] = 0, flow[m] = 0, cost[m] = -w, link[m] = last[v], last[v] = m++;
  90.     }
  91.     bool spfa(){
  92.         int i, j, x, f = 0, l = 0;
  93.         for (i = 0; i <= n; i++) visited[i] = 0, dis[i] = INF;
  94.  
  95.         dis[s] = 0, Q[l++] = s;
  96.         while (f < l){
  97.             i = Q[f++];
  98.             for (j = last[i]; j != -1; j = link[j]){
  99.                 if (flow[j] < cap[j]){
  100.                     x = adj[j];
  101.                     if (dis[x] > dis[i] + cost[j]){
  102.                         dis[x] = dis[i] + cost[j], from[x] = j;
  103.                         if (!visited[x]){
  104.                             visited[x] = 1;
  105.                             if (f && rand() & 7) Q[--f] = x;
  106.                             else Q[l++] = x;
  107.                         }
  108.                     }
  109.                 }
  110.             }
  111.             visited[i] = 0;
  112.         }
  113.         return (dis[t] != INF);
  114.     }
  115.     pair <long long, long long> solve(){
  116.         int i, j;
  117.         long long mincost = 0, maxflow = 0;
  118.         while (spfa()){
  119.             long long aug = INF;
  120.             for (i = t, j = from[i]; i != s; i = adj[j ^ 1], j = from[i]){
  121.                 aug = min(aug, cap[j] - flow[j]);
  122.             }
  123.             for (i = t, j = from[i]; i != s; i = adj[j ^ 1], j = from[i]){
  124.                 flow[j] += aug, flow[j ^ 1] -= aug;
  125.             }
  126.             maxflow += aug, mincost += aug * dis[t];
  127.         }
  128.         return make_pair(mincost, maxflow);
  129.     }
  130. }
  131. vector < pair<int,int> > G[205] ;
  132. int leaves[205] ;
  133. int isLeaf[205] ;
  134. int lvl[205] ;
  135. int cst[205] ;
  136. void dfs (int u , int p , int l) {
  137.     lvl[u] = l ;
  138.     if (G[u].size() == 1 and u != 1) {
  139.         leaves[u] = 1;
  140.         isLeaf[u] = 1;
  141.         return ;
  142.     }
  143.     isLeaf[u] = leaves[u] = 0 ;
  144.     for(int i = 0 ; i < G[u].size() ; i++) {
  145.         int v = G[u][i].first ;
  146.         if (v!=p) {
  147.             dfs(v,u,l+1) ;
  148.             leaves[u] += leaves[v] ;
  149.         }
  150.     }
  151. }
  152. int main(){
  153.     int tc , caseno = 1 ;
  154.     scanf("%d" , &tc) ;
  155.     while (tc--) {
  156.         int n ; scanf("%d" , &n) ;
  157.         for (int i = 1 ; i <= n ; i++) {
  158.             G[i].clear() ;
  159.         }
  160.         int maxw = 40 ;
  161.         for (int i = 1 ; i < n ; i++) {
  162.             int u , v, w ;
  163.             scanf("%d %d %d", &u,&v,&w) ;
  164.             cst[i] = w ; maxw = max(maxw,w) ;
  165.             G[u].push_back(make_pair(v,i)) ;
  166.             G[v].push_back(make_pair(u,i)) ;
  167.         }
  168.         dfs(1,-1,1) ;
  169.         int source = 0 , nodes = n+1 , sink = 1 ;
  170.         mcmf :: init(nodes , source , sink) ;
  171.         for (int i = 1 ; i <= n ; i++) {
  172.             if (isLeaf[i]) {
  173.                 mcmf :: addEdge(source,i,maxw,0) ;
  174.             }
  175.             for (int j = 0 ; j < G[i].size() ; j++) {
  176.                 int v = G[i][j].first , c = cst[G[i][j].second] ;
  177.                 int u = i ;
  178.                 if (lvl[u] > lvl[v]) {
  179.                     mcmf :: addEdge(u,v,leaves[u]*maxw-c,0) ;
  180.                 }
  181.             }
  182.         }
  183.         int m ; scanf("%d" , &m) ;
  184.         while (m--) {
  185.             int u , v , cap , w ;
  186.             scanf("%d %d %d %d" , &u , &v , &cap , &w) ;
  187.             if (lvl[v] > lvl[u]) swap(u,v) ;
  188.             mcmf :: addEdge(u,v,cap,w) ;
  189.         }
  190.         printf ("Case #%d: " , caseno++) ;
  191.         pair<int,int> res = mcmf::solve() ;
  192.         if (res.second != maxw*leaves[1]) {
  193.             printf ("-1\n") ;
  194.         }
  195.         else {
  196.             printf ("%d\n" , res.first) ;
  197.         }
  198.     }
  199. }
  200.  
  201.  
  202.  
  203. /// Minimum path cover/Maximum independent set in DAG
  204. #define MAX 505
  205. namespace dag{
  206.     bool ar[MAX][MAX]; /// For transitive closure and minimum path cover with not necessarily disjoint vertex
  207.     vector <int> adj[MAX];
  208.     bool visited[MAX], first_set[MAX], second_set[MAX];
  209.     int n, L[MAX], R[MAX], D[MAX], Q[MAX], dis[MAX], parent[MAX];
  210.     inline void init(int nodes){ /// Number of vertices in DAG
  211.         n = nodes;
  212.         for (int i = 0; i < MAX; i++) adj[i].clear();
  213.     }
  214.     inline void add_edge(int u, int v){ /// 0 based index, directed edge of DAG
  215.         adj[u].push_back(v);
  216.     }
  217.     bool dfs(int i){
  218.         int len = adj[i].size();
  219.         for (int j = 0; j < len; j++){
  220.             int x = adj[i][j];
  221.             if (L[x] == -1 || (parent[L[x]] == i)){
  222.                 if (L[x] == -1 || dfs(L[x])){
  223.                     L[x] = i, R[i] = x;
  224.                     return true;
  225.                 }
  226.             }
  227.         }
  228.         return false;
  229.     }
  230.     bool bfs(){
  231.         clr(visited);
  232.         int i, j, x, d, f = 0, l = 0;
  233.         for (i = 0; i < n; i++){
  234.             if (R[i] == -1){
  235.                 visited[i] = true;
  236.                 Q[l++] = i, dis[i] = 0;
  237.             }
  238.         }
  239.         while (f < l){
  240.             i = Q[f++];
  241.             int len = adj[i].size();
  242.             for (j = 0; j < len; j++){
  243.                 x = adj[i][j], d = L[x];
  244.                 if (d == -1) return true;
  245.                 else if (!visited[d]){
  246.                     Q[l++] = d;
  247.                     parent[d] = i, visited[d] = true, dis[d] = dis[i] + 1;
  248.                 }
  249.             }
  250.         }
  251.         return false;
  252.     }
  253.     void get_path(int i){
  254.         first_set[i] = true;
  255.         int j, x, len = adj[i].size();
  256.         for (j = 0; j < len; j++){
  257.             x = adj[i][j];
  258.             if (!second_set[x] && L[x] != -1){
  259.                 second_set[x] = true;
  260.                 get_path(L[x]);
  261.             }
  262.         }
  263.     }
  264.     void transitive_closure(){ /// Transitive closure in O(n * m)
  265.         clr(ar);
  266.         int i, j, k, l;
  267.         for (i = 0; i < n; i++){
  268.             l = adj[i].size();
  269.             for (j = 0; j < l; j++){
  270.                 ar[i][adj[i][j]] = true;
  271.             }
  272.             adj[i].clear();
  273.         }
  274.         for (k = 0; k < n; k++){
  275.             for (i = 0; i < n; i++){
  276.                 if (ar[i][k]){
  277.                     for (j = 0; j < n; j++){
  278.                         if (ar[k][j]) ar[i][j] = true;
  279.                     }
  280.                 }
  281.             }
  282.         }
  283.         for (i = 0; i < n; i++){
  284.             for (j = 0; j < n; j++){
  285.                 if (i != j && ar[i][j]){
  286.                     adj[i].push_back(j);
  287.                 }
  288.             }
  289.         }
  290.     }
  291.     int minimum_disjoint_path_cover(){ /// Minimum vertex disjoint path cover in DAG. Handle isolated vertices appropriately
  292.         int i, res = 0;
  293.         memset(L, -1, sizeof(L));
  294.         memset(R, -1, sizeof(R));
  295.         while (bfs()){
  296.             for (i = 0; i < n; i++){
  297.                 if (R[i] == -1 && dfs(i)) res++;
  298.             }
  299.         }
  300.         return n - res;
  301.     }
  302.     int minimum_path_cover(){ /// Minimum path cover in DAG. Handle isolated vertices appropriately
  303.         transitive_closure();
  304.         return minimum_disjoint_path_cover();
  305.     }
  306.     vector <int> minimum_vertex_cover(){ /// Minimum vertex cover of DAG, equal to maximum bipartite matching
  307.         int i, res = 0;
  308.         memset(L, -1, sizeof(L));
  309.         memset(R, -1, sizeof(R));
  310.         while (bfs()){
  311.             for (i = 0; i < n; i++){
  312.                 if (R[i] == -1 && dfs(i)) res++;
  313.             }
  314.         }
  315.         vector <int> v;
  316.         clr(first_set), clr(second_set);
  317.         for (i = 0; i < n; i++){
  318.             if (R[i] == -1) get_path(i);
  319.         }
  320.         for (i = 0; i < n; i++){
  321.             if (!first_set[i] || second_set[i]) v.push_back(i);
  322.         }
  323.         return v;
  324.     }
  325.     vector <int> maximum_independent_set(){ /// Maximum independent set of DAG, all vertices not in minimum vertex cover
  326.         vector <int> v = minimum_vertex_cover();
  327.         clr(visited);
  328.         int i, len = v.size();
  329.         for (i = 0; i < len; i++) visited[v[i]] = true;
  330.         vector <int> res;
  331.         for (i = 0; i < n; i++){
  332.             if (!visited[i]) res.push_back(i);
  333.         }
  334.         return res;
  335.     }
  336. }
  337.  
  338.  
  339.  
  340. /// Johnson's algo
  341. /// Johnson's algorithm for all pair shortest paths in sparse graphs
  342. /// Complexity: O(N * M) + O(N * M * log(N))
  343. #define MAX 2525
  344. const long long INF = (1LL << 60) - 666;
  345. struct edge{
  346.     int u, v;
  347.     long long w;
  348.     edge(){}
  349.     edge(int u, int v, long long w) : u(u), v(v), w(w){}
  350.     void print(){
  351.         cout << "edge " << u << " " << v << " " << w << endl;
  352.     }
  353. };
  354. bool bellman_ford(int n, int src, vector <struct edge> E, vector <long long>& dis){
  355.     dis[src] = 0;
  356.     for (int i = 0; i <= n; i++){
  357.         int flag = 0;
  358.         for (auto e: E){
  359.             if ((dis[e.u] + e.w) < dis[e.v]){
  360.                 flag = 1;
  361.                 dis[e.v] = dis[e.u] + e.w;
  362.             }
  363.         }
  364.         if (flag == 0) return true;
  365.     }
  366.     return false;
  367. }
  368. vector <long long> dijkstra(int n, int src, vector <struct edge> E, vector <long long> potential){
  369.     set<pair<long long, int> > S;
  370.     vector <long long> dis(n + 1, INF);
  371.     vector <long long> temp(n + 1, INF);
  372.     vector <pair<int, long long> > adj[n + 1];
  373.     dis[src] = temp[src] = 0;
  374.     S.insert(make_pair(temp[src], src));
  375.     for (auto e: E){
  376.         adj[e.u].push_back(make_pair(e.v, e.w));
  377.     }
  378.     while (!S.empty()){
  379.         pair<long long, int> cur = *(S.begin());
  380.         S.erase(cur);
  381.         int u = cur.second;
  382.         for (int i = 0; i < adj[u].size(); i++){
  383.             int v = adj[u][i].first;
  384.             long long w = adj[u][i].second;
  385.             if ((temp[u] + w) < temp[v]){
  386.                 S.erase(make_pair(temp[v], v));
  387.                 temp[v] = temp[u] + w;
  388.                 dis[v] = dis[u] + w;
  389.                 S.insert(make_pair(temp[v], v));
  390.             }
  391.         }
  392.     }
  393.     return dis;
  394. }
  395. void johnson(int n, long long ar[MAX][MAX], vector <struct edge> E){
  396.     vector <long long> potential(n + 1, INF);
  397.     for (int i = 1; i <= n; i++) E.push_back(edge(0, i, 0));
  398.     assert(bellman_ford(n, 0, E, potential));
  399.     for (int i = 1; i <= n; i++) E.pop_back();
  400.     for (int i = 1; i <= n; i++){
  401.         vector <long long> dis = dijkstra(n, i, E, potential);
  402.         for (int j = 1; j <= n; j++){
  403.             ar[i][j] = dis[j];
  404.         }
  405.     }
  406. }
  407. long long ar[MAX][MAX];
  408. int main(){
  409.     vector <struct edge> E;
  410.     E.push_back(edge(1, 2, 2));
  411.     E.push_back(edge(2, 3, -15));
  412.     E.push_back(edge(1, 3, -10));
  413.     int n = 3;
  414.     johnson(n, ar, E);
  415.     for (int i = 1; i <= n; i++){
  416.         for (int j = 1; j <= n; j++){
  417.             printf("%d %d = %lld\n", i, j, ar[i][j]);
  418.         }
  419.     }
  420.     return 0;
  421. }
  422.  
  423.  
  424.  
  425. /// Hungarian algo
  426. #define MAX 666
  427. #define MAXIMIZE +1
  428. #define MINIMIZE -1
  429. #define inf (~0U >> 1)
  430. namespace wm{ /// hash = 581023
  431.     bool visited[MAX];
  432.     int U[MAX], V[MAX], P[MAX], way[MAX], minv[MAX], match[MAX], ar[MAX][MAX];
  433.     /// n = number of row and m = number of columns in 1 based, flag = MAXIMIZE or MINIMIZE
  434.     /// match[i] contains the column to which row i is matched
  435.     int hungarian(int n, int m, int mat[MAX][MAX], int flag){
  436.         clr(U), clr(V), clr(P), clr(ar), clr(way);
  437.         for (int i = 1; i <= n; i++){
  438.             for (int j = 1; j <= m; j++){
  439.                 ar[i][j] = mat[i][j];
  440.                 if (flag == MAXIMIZE) ar[i][j] = -ar[i][j];
  441.             }
  442.         }
  443.         if (n > m) m = n;
  444.         int i, j, a, b, c, d, r, w;
  445.         for (i = 1; i <= n; i++){
  446.             P[0] = i, b = 0;
  447.             for (j = 0; j <= m; j++) minv[j] = inf, visited[j] = false;
  448.             do{
  449.                 visited[b] = true;
  450.                 a = P[b], d = 0, w = inf;
  451.                 for (j = 1; j <= m; j++){
  452.                     if (!visited[j]){
  453.                         r = ar[a][j] - U[a] - V[j];
  454.                         if (r < minv[j]) minv[j] = r, way[j] = b;
  455.                         if (minv[j] < w) w = minv[j], d = j;
  456.                     }
  457.                 }
  458.                 for (j = 0; j <= m; j++){
  459.                     if (visited[j]) U[P[j]] += w, V[j] -= w;
  460.                     else minv[j] -= w;
  461.                 }
  462.                 b = d;
  463.             } while (P[b] != 0);
  464.             do{
  465.                 d = way[b];
  466.                 P[b] = P[d], b = d;
  467.             } while (b != 0);
  468.         }
  469.         for (j = 1; j <= m; j++) match[P[j]] = j;
  470.         return (flag == MINIMIZE) ? -V[0] : V[0];
  471.     }
  472. }
  473.  
  474.  
  475.  
  476. /// Hopcroft karp in O(m * sqrt(n))
  477. #define MAX 100010
  478. namespace hc{ /// hash = 393558
  479.     bool visited[MAX];
  480.     vector <int> adj[MAX];
  481.     int n, L[MAX], R[MAX], Q[MAX], len[MAX], dis[MAX], parent[MAX];
  482.     inline void init(int nodes){ /// Number of vertices in the left set, or max(left_set, right_set)
  483.         n = nodes, clr(len);
  484.         for (int i = 0; i < MAX; i++) adj[i].clear();
  485.     }
  486.     inline void add_edge(int u, int v){ /// 0 based index
  487.         len[u]++;
  488.         adj[u].push_back(v);
  489.     }
  490.     bool dfs(int i){
  491.         for (int j = 0; j < len[i]; j++){
  492.             int x = adj[i][j];
  493.             if (L[x] == -1 || (parent[L[x]] == i)){
  494.                 if (L[x] == -1 || dfs(L[x])){
  495.                     L[x] = i, R[i] = x;
  496.                     return true;
  497.                 }
  498.             }
  499.         }
  500.         return false;
  501.     }
  502.     bool bfs(){
  503.         clr(visited);
  504.         int i, j, x, d, f = 0, l = 0;
  505.         for (i = 0; i < n; i++){
  506.             if (R[i] == -1){
  507.                 visited[i] = true;
  508.                 Q[l++] = i, dis[i] = 0;
  509.             }
  510.         }
  511.         while (f < l){
  512.             i = Q[f++];
  513.             for (j = 0; j < len[i]; j++){
  514.                 x = adj[i][j], d = L[x];
  515.                 if (d == -1) return true;
  516.  
  517.                 else if (!visited[d]){
  518.                     Q[l++] = d;
  519.                     parent[d] = i, visited[d] = true, dis[d] = dis[i] + 1;
  520.                 }
  521.             }
  522.         }
  523.         return false;
  524.     }
  525.     int hopcroft_karp(){
  526.         int res = 0;
  527.         memset(L, -1, sizeof(L));
  528.         memset(R, -1, sizeof(R));
  529.         while (bfs()){
  530.             for (int i = 0; i < n; i++){
  531.                 if (R[i] == -1 && dfs(i)) res++;
  532.             }
  533.         }
  534.         return res;
  535.     }
  536. }
  537. int main(){
  538.     int n, m, r, i, j, a, b;
  539.     scanf("%d %d %d", &n, &m, &r);
  540.     hc::init(max(n, m));
  541.     while (r--){
  542.         scanf("%d %d", &a, &b);
  543.         hc::add_edge(--a, --b);
  544.     }
  545.     printf("%d\n", hc::hopcroft_karp());
  546.     return 0;
  547. }
  548.  
  549.  
  550.  
  551. /// Dinic's algorithm for directed graphs (0 based index for graphs)
  552. /// For undirected graphs, just add two directed edges
  553. #define MAXN 50010
  554. const long long INF = (~0ULL) >> 1;
  555. namespace flow{
  556.     struct Edge{
  557.         int u, v;
  558.         long long cap, flow;
  559.         Edge(){}
  560.         Edge(int a, int b, long long c, long long f){
  561.             u = a, v = b, cap = c, flow = f;
  562.         }
  563.     };
  564.     vector <int> adj[MAXN];
  565.     vector <struct Edge> E;
  566.     int n, s, t, ptr[MAXN], len[MAXN], dis[MAXN], Q[MAXN];
  567.     inline void init(int nodes, int source, int sink){
  568.         clr(len);
  569.         E.clear();
  570.         n = nodes, s = source, t = sink;
  571.         for (int i = 0; i < MAXN; i++) adj[i].clear();
  572.     }
  573.     /// Adds a directed edge with capacity c
  574.     inline void addEdge(int a, int b, long long c){
  575.         adj[a].push_back(E.size());
  576.         E.push_back(Edge(a, b, c, 0));
  577.         len[a]++;
  578.         adj[b].push_back(E.size());
  579.         E.push_back(Edge(b, a, 0, 0));
  580.         len[b]++;
  581.     }
  582.     inline bool bfs(){
  583.         int i, j, k, id, f = 0, l = 0;
  584.         memset(dis, -1, sizeof(dis[0]) * n);
  585.         dis[s] = 0, Q[l++] = s;
  586.         while (f < l && dis[t] == -1){
  587.             i = Q[f++];
  588.             for (k = 0; k < len[i]; k++){
  589.                 id = adj[i][k];
  590.                 if (dis[E[id].v] == -1 && E[id].flow < E[id].cap){
  591.                     Q[l++] = E[id].v;
  592.                     dis[E[id].v] = dis[i] + 1;
  593.                 }
  594.             }
  595.         }
  596.         return (dis[t] != -1);
  597.     }
  598.     long long dfs(int i, long long f){
  599.         if (i == t || !f) return f;
  600.         while (ptr[i] < len[i]){
  601.             int id = adj[i][ptr[i]];
  602.             if (dis[E[id].v] == dis[i] + 1){
  603.                 long long x = dfs(E[id].v, min(f, E[id].cap - E[id].flow));
  604.                 if (x){
  605.                     E[id].flow += x, E[id ^ 1].flow -= x;
  606.                     return x;
  607.                 }
  608.             }
  609.             ptr[i]++;
  610.         }
  611.         return 0;
  612.     }
  613.     long long dinic(){
  614.         long long res = 0;
  615.         while (bfs()){
  616.             memset(ptr, 0, n * sizeof(ptr[0]));
  617.             while (long long f = dfs(s, INF)) {
  618.                 res += f;
  619.             }
  620.         }
  621.         return res;
  622.     }
  623. }
  624. namespace nodeflow{
  625.     void init(int n, int s, int t, vector <long long> capacity){
  626.         flow::init(n * 2, s * 2, t * 2 + 1);
  627.         for (int i = 0; i < n; i++){
  628.             flow::addEdge(i * 2, i * 2 + 1, capacity[i]);
  629.         }
  630.     }
  631.     void addEdge(int a, int b, long long c){
  632.         flow::addEdge(a * 2 + 1, b * 2, c);
  633.     }
  634.     long long dinic(){
  635.         return flow::dinic();
  636.     }
  637. }
  638. int main(){
  639.     int n , b , q ;
  640.     cin >> n >> b >> q ;
  641.     vector < pair<int,int> > v ;
  642.     v.push_back({b,n}) ;
  643.     v.push_back({0,0}) ;
  644.     for (int i = 1 ; i <= q ; i++) {
  645.         int x , k ;
  646.         cin >> x >> k ;
  647.         v.push_back({x,k}) ;
  648.     }
  649.     sort(v.begin(), v.end()) ;
  650.     v.erase(unique(v.begin(),v.end()),v.end()) ;
  651.     int source = 0 , nodes = 1 + 5 + v.size() , sink = nodes-1 ;
  652.     flow :: init(nodes,source,sink) ;
  653.     for (int i = 1 ; i <= 5 ; i++) {
  654.         flow :: addEdge(source,i,n/5) ;
  655.     }
  656.     for (int i = 1 ; i < v.size() ; i++) {
  657.         int cnt = v[i].second - v[i-1].second ;
  658.         if (cnt < 0) {
  659.             printf ("unfair") ;
  660.             return 0 ;
  661.         }
  662.         flow :: addEdge(i+5,sink,+cnt) ;
  663.         int l = v[i-1].first+1 , r = v[i].first ;
  664.         if (l > r) {
  665.             printf ("unfair") ;
  666.             return 0 ;
  667.         }
  668.         int count_[5] ;
  669.         memset (count_ , 0 , sizeof count_) ;
  670.         for (int x = l ; x <= r ; x++) {
  671.             count_[x%5]++ ;
  672.         }
  673.         for (int j = 1 ; j <= 5 ; j++) {
  674.             flow::addEdge(j,i+5,count_[j-1]) ;
  675.         }
  676.     }
  677.     if (flow::dinic() == n) {
  678.         printf ("fair") ;
  679.     }
  680.     else {
  681.         printf ("unfair") ;
  682.     }
  683.     return 0;
  684. }
  685.  
  686.  
  687.  
  688. /// Dinic's algorithm for directed graphs (0 based index for graphs)
  689. /// For undirected graphs, just add two directed edges
  690. #define MAXN 5010
  691. const long long INF = (~0ULL) >> 1;
  692. namespace flow{
  693.     int n, s, t, ptr[MAXN], dis[MAXN], Q[MAXN];
  694.     long long cap[MAXN][MAXN], flow[MAXN][MAXN];
  695.     inline void init(int nodes, int source, int sink){
  696.         clr(cap), clr(flow);
  697.         n = nodes, s = source, t = sink;
  698.     }
  699.     inline void addEdge(int a, int b, int c){
  700.         cap[a][b] += c;
  701.     }
  702.     inline bool bfs(){
  703.         int i, j, f = 0, l = 0;
  704.         memset(dis, -1, sizeof(dis[0]) * n);
  705.         dis[s] = 0, Q[l++] = s;
  706.         while (f < l){
  707.             i = Q[f++];
  708.             for (j = 0; j < n; j++){
  709.                 if (dis[j] == -1 && flow[i][j] < cap[i][j]){
  710.                     Q[l++] = j;
  711.                     dis[j] = dis[i] + 1;
  712.                 }
  713.             }
  714.         }
  715.         return (dis[t] != -1);
  716.     }
  717.     long long dfs(int i, long long f){
  718.         if (i == t || !f) return f;
  719.         for (int &j = ptr[i]; j < n; j++){
  720.             if (dis[j] == (dis[i] + 1)){
  721.                 long long x = dfs(j, min(f, cap[i][j] - flow[i][j]));
  722.                 if (x){
  723.                     flow[i][j] += x, flow[j][i] -= x;
  724.                     return x;
  725.                 }
  726.             }
  727.         }
  728.         return 0;
  729.     }
  730.     long long dinic(){
  731.         long long res = 0;
  732.         while (bfs()){
  733.             memset(ptr, 0, n * sizeof(ptr[0]));
  734.             while (long long f = dfs(s, INF)){
  735.                 res += f;
  736.             }
  737.         }
  738.         return res;
  739.     }
  740. }
  741. int main(){
  742.     int n, i, j, k, a, b, c, s, t, m;
  743.     n = MAXN - 10;
  744.     s = 0, t = n - 1;
  745.     flow::init(n, s, t);
  746.     m = n * 1.75;
  747.     while (m--){
  748.         a = ran(0, n - 1);
  749.         b = ran(0, n - 1);
  750.         c = ran(1, 1000000000);
  751.         flow::addEdge(a, b, c);
  752.     }
  753.     clock_t start = clock();
  754.     printf("%lld\n", flow::dinic());
  755.     fprintf(stderr, "%0.6f\n", (clock() - start) / (1.0 * CLOCKS_PER_SEC));
  756.     return 0;
  757. }
  758.  
  759.  
  760.  
  761. /// Directed minimum spanning tree in O(n * m)
  762. /// Constructs a rooted tree of minimum total weight from the root node
  763. /// Returns -1 if no solution from root
  764. struct Edge{
  765.     int u, v, w;
  766.     Edge(){}
  767.     Edge(int a, int b, int c){
  768.         u = a, v = b, w = c;
  769.     }
  770. };
  771. int directed_MST(int n, vector <Edge> E, int root){ /// hash = 547539
  772.     const int INF = (1 << 30) - 30;
  773.     int i, j, k, l, x, y, res = 0;
  774.     vector <int> cost(n), parent(n), label(n), comp(n);
  775.     for (; ;){
  776.         for (i = 0; i < n; i++) cost[i] = INF;
  777.         for (auto e: E){
  778.             if (e.u != e.v && cost[e.v] > e.w){
  779.                 cost[e.v] = e.w;
  780.                 parent[e.v] = e.u;
  781.             }
  782.         }
  783.         cost[root] = 0;
  784.         for (i = 0; i < n && cost[i] != INF; i++){};
  785.         if (i != n) return -1; /// No solution
  786.         for (i = 0, k = 0; i < n; i++) res += cost[i];
  787.         for (i = 0; i < n; i++) label[i] = comp[i] = -1;
  788.         for (i = 0; i < n; i++){
  789.             for (x = i; x != root && comp[x] == -1; x = parent[x]) comp[x] = i;
  790.             if (x != root && comp[x] == i){
  791.                 for (k++; label[x] == -1; x = parent[x]) label[x] = k - 1;
  792.             }
  793.         }
  794.         if (k == 0) break;
  795.         for (i = 0; i < n; i++){
  796.             if (label[i] == -1) label[i] = k++;
  797.         }
  798.         for (auto &e: E){
  799.             x = label[e.u], y = label[e.v];
  800.             if (x != y) e.w -= cost[e.v];
  801.             e.u = x, e.v = y;
  802.         }
  803.         root = label[root], n = k;
  804.     }
  805.     return res;
  806. }
  807. int main(){
  808.     int T = 0, t, n, m, i, j, k, u, v, w, res;
  809.     scanf("%d", &t);
  810.     while (t--){
  811.         vector <Edge> E;
  812.         scanf("%d %d", &n, &m);
  813.         for (i = 0; i < m; i++){
  814.             scanf("%d %d %d", &u, &v, &w);
  815.             E.push_back(Edge(u, v, w));
  816.         }
  817.         res = directed_MST(n, E, 0);
  818.         if (res == -1) printf("Case #%d: Possums!\n", ++T);
  819.         else printf("Case #%d: %d\n", ++T, res);
  820.     }
  821.     return 0;
  822. }
  823.  
  824.  
  825.  
  826. /// Bridge (Extended)
  827. #define MAX 100010
  828. /// Note: 0-based indexing for graphs
  829. struct bridge{
  830.     int u, v, w; /// Bridge from node u to v with cost w
  831.     int f, s; /// Number of components in the first and second graph if bridge is disconnected
  832.     bridge(){
  833.     }
  834.     bridge(int a, int b, int c, int d, int e){
  835.         if (a > b) swap(a, b); /// Lower node first for convenience
  836.         u = a, v = b, w = c, f = d, s = e;
  837.     }
  838. };
  839. namespace br{
  840.     typedef pair<int, int> Pair;
  841.     bool visited[MAX];
  842.     vector <bridge> B;
  843.     vector <Pair> adj[MAX];
  844.     tr1::unordered_set <long long> S;
  845.     int n, r, dt, discover[MAX], low[MAX], cmp[MAX], num[MAX];
  846.     void init(int nodes){
  847.         n = nodes;
  848.         for (int i = 0; i < MAX; i++) adj[i].clear();
  849.     }
  850.     void dfs(int i, int p){ /// hash = 60375
  851.         visited[i] = true;
  852.         discover[i] = low[i] = ++dt;
  853.         int j, x, l, children = 0, len = adj[i].size();
  854.         for (j = 0; j < len; j++){
  855.             x = adj[i][j].first;
  856.             if (!visited[x]){
  857.                 dfs(x, i);
  858.                 children++;
  859.                 low[i] = min(low[i], low[x]);
  860.                 if (low[x] > discover[i]){
  861.                     if (!(j && adj[i][j - 1].first == x) || ( (j + 1) < len && adj[i][j + 1].first == x) ){ /// Handling multi-edge
  862.                         l = dt - discover[x] + 1;
  863.                         B.push_back( bridge(i, x, adj[i][j].second, l, cmp[i] - l) );
  864.                     }
  865.                 }
  866.             }
  867.             else if (x != p) low[i] = min(low[i], discover[x]);
  868.         }
  869.     }
  870.     void dfs(int i){
  871.         low[dt++] = i;
  872.         visited[i] = true;
  873.         int j, x, len = adj[i].size();
  874.         for (j = 0; j < len; j++){
  875.             x = adj[i][j].first;
  876.             if (!visited[x]){
  877.                 dfs(x);
  878.             }
  879.         }
  880.     }
  881.     /// Adds undirected edge from a to b with cost c or edge index number i
  882.     void add(int a, int b, int c){
  883.         adj[a].push_back(Pair(b, c));
  884.         adj[b].push_back(Pair(a, c));
  885.     }
  886.     void FindBridge(){
  887.         int i, j;
  888.         B.clear();
  889.         memset(visited, 0, sizeof(visited));
  890.         for (i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end()); /// To handle multi-edges
  891.         for (i = 0; i < n; i++){
  892.             if (!visited[i]){
  893.                 dt = 0;
  894.                 dfs(i);
  895.                 for (j = 0; j < dt; j++) cmp[low[j]] = dt;
  896.             }
  897.         }
  898.         memset(visited, 0, sizeof(visited));
  899.         for (i = 0; i < n; i++){
  900.             if (!visited[i]){
  901.                 dt = 0;
  902.                 dfs(i, -1);
  903.             }
  904.         }
  905.     }
  906.     long long hashval(long long u, long long v){
  907.         return (u * MAX) + v;
  908.     }
  909.     void dfsnum(int i){
  910.         num[i] = r;
  911.         visited[i] = true;
  912.         int j, x, len = adj[i].size();
  913.         for (j = 0; j < len; j++){
  914.             x = adj[i][j].first;
  915.             if (!visited[x] && !S.count(hashval(i, x))){
  916.                 dfsnum(x);
  917.             }
  918.         }
  919.     }
  920.     /// Call FindBridge before
  921.     void BridgeTree(){
  922.         S.clear();
  923.         int i, j, x, u, v, len = B.size();
  924.         for (i = 0; i < len; i++){
  925.             S.insert(hashval(B[i].u, B[i].v));
  926.             S.insert(hashval(B[i].v, B[i].u));
  927.         }
  928.         r = 0; /// Number of nodes in bridge tree
  929.         memset(visited, 0, sizeof(visited));
  930.         for (i = 0; i < n; i++){
  931.             if (!visited[i]){
  932.                 dfsnum(i);
  933.                 r++;
  934.             }
  935.         }
  936.         for (i = 0; i < len; i++){
  937.             u = B[i].u, v = B[i].v;
  938.             /// Build the bridge tree here accordingly
  939.         }
  940.     }
  941. }
  942.  
  943.  
  944.  
  945. /// bipartite matching
  946. #define MAX 1010
  947. bool visited[MAX];
  948. int t, line, n, m, ar[MAX][MAX], adj[MAX][MAX], left[MAX], right[MAX], len[MAX];
  949. bool bipartite_matching(int u){
  950.     int v = 0, j = 0;
  951.     for (j = 0; j < len[u]; j++){
  952.         v = adj[u][j];
  953.         if (visited[v]) continue;
  954.         visited[v] = true;
  955.         if (right[v] == -1 || bipartite_matching(right[v])){
  956.             left[u] = v;
  957.             right[v] = u;
  958.             return true;
  959.         }
  960.     }
  961.     return false;
  962. }
  963. int max_matching(){
  964.     memset(left, -1, sizeof(left));
  965.     memset(right, -1, sizeof(right));
  966.     int i, counter = 0;
  967.     for (i = 0; i < n; i++){
  968.         memset(visited, 0, sizeof(visited));
  969.         if (bipartite_matching(i)) counter++;
  970.     }
  971.     return counter;
  972. }
  973. int main(){
  974.     int a, b;
  975.     while (scanf("%d %d", &n, &m) != EOF){
  976.         memset(len, 0, sizeof(len));
  977.         while (m--){
  978.             scanf("%d %d", &a, &b);
  979.             adj[a][len[a]++] = b;
  980.         }
  981.     }
  982.     return 0;
  983. }
  984.  
  985.  
  986.  
  987. /// 2 SAT (1 based index for variables)
  988. /// Each variable can have two possible values (true or false)
  989. /// Variables must satisfy a system of constraints on pairs of variables
  990. #define MAX 100010
  991. namespace sat{
  992.     bool visited[MAX * 2];
  993.     vector <int> adj[MAX * 2], rev[MAX * 2];
  994.     int n, m, l, dfs_t[MAX * 2], order[MAX * 2], parent[MAX * 2];
  995.     inline int neg(int x){
  996.         return ((x) <= n ? (x + n) : (x - n));
  997.     }
  998.     /// Call init once
  999.     void init(int nodes){
  1000.         n = nodes, m = nodes * 2;
  1001.         for (int i = 0; i < MAX * 2; i++){
  1002.             adj[i].clear();
  1003.             rev[i].clear();
  1004.         }
  1005.     }
  1006.     /// Add implication, if a then b
  1007.     inline void add_implication(int a, int b){
  1008.         if (a < 0) a = n - a;
  1009.         if (b < 0) b = n - b;
  1010.         adj[a].push_back(b);
  1011.         rev[b].push_back(a);
  1012.     }
  1013.     inline void add_or(int a, int b){
  1014.         add_implication(-a, b);
  1015.         add_implication(-b, a);
  1016.     }
  1017.     inline void add_xor(int a, int b){
  1018.         add_or(a, b);
  1019.         add_or(-a, -b);
  1020.     }
  1021.     inline void add_and(int a, int b){
  1022.         add_or(a, b);
  1023.         add_or(a, -b);
  1024.         add_or(-a, b);
  1025.     }
  1026.     /// force variable x to be true (if x is negative, force !x to be true)
  1027.     inline void force_true(int x){
  1028.         if (x < 0) x = n - x;
  1029.         add_implication(neg(x), x);
  1030.     }
  1031.     /// force variable x to be false (if x is negative, force !x to be false)
  1032.     inline void force_false(int x){
  1033.         if (x < 0) x = n - x;
  1034.         add_implication(x, neg(x));
  1035.     }
  1036.     inline void topsort(int i){
  1037.         visited[i] = true;
  1038.         int j, x, len = rev[i].size();
  1039.  
  1040.         for (j = 0; j < len; j++){
  1041.             x = rev[i][j];
  1042.             if (!visited[x]) topsort(x);
  1043.         }
  1044.         dfs_t[i] = ++l;
  1045.     }
  1046.     inline void dfs(int i, int p){
  1047.         parent[i] = p;
  1048.         visited[i] = true;
  1049.         int j, x, len = adj[i].size();
  1050.         for (j = 0; j < len; j++){
  1051.             x = adj[i][j];
  1052.             if (!visited[x]) dfs(x, p);
  1053.         }
  1054.     }
  1055.     void build(){
  1056.         int i, x;
  1057.         memset(visited, 0, sizeof(visited));
  1058.         for (i = m, l = 0; i >= 1; i--){
  1059.             if (!visited[i]){
  1060.                 topsort(i);
  1061.             }
  1062.             order[dfs_t[i]] = i;
  1063.         }
  1064.         memset(visited, 0, sizeof(visited));
  1065.         for (i = m; i >= 1; i--){
  1066.             x = order[i];
  1067.             if (!visited[x]){
  1068.                 dfs(x, x);
  1069.             }
  1070.         }
  1071.     }
  1072.     /// Returns true if the system is 2-satisfiable and returns the solution (nodes set to true) in vector res
  1073.     bool satisfy(vector <int>& res){
  1074.         build();
  1075.         memset(visited, 0, sizeof(visited));
  1076.         for (int i = 1; i <= m; i++){
  1077.             int x = order[i];
  1078.             if (parent[x] == parent[neg(x)]) return false;
  1079.             if (!visited[parent[x]]){
  1080.                 visited[parent[x]] = true;
  1081.                 visited[parent[neg(x)]] = false;
  1082.             }
  1083.         }
  1084.         res.clear();
  1085.         for (int i = 1; i <= n; i++){
  1086.             if (visited[parent[i]]) res.push_back(i);
  1087.         }
  1088.         return true;
  1089.     }
  1090. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top