API tools faq
paste
Advertisement
_no0B

Untitled

_no0B
Apr 25th, 2019
231
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 32.30 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!