beloved_ACM

康托展开的应用实例　　{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。 　　代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。 　　他们间的对应关系可由康托展开来找到。 　　如我想知道321是{1,2,3}中第几个大的数可以这样考虑 ： 　　第一位是3，当第一位的数小于3时，那排列数小于321 如 123、 213 ，小于3的数有1、2 。所以有2*2!个。再看小于第二位2的：小于2的数只有一个就是1 ，所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。 2*2!+1*1!是康托展开。 　　再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1和2，但1已经在第一位了，所以只有一个数2 1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数 0*1! ，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。

  我比较懒，可以参考《图论总结》。

#include <iostream>
#include <queue>
#include <stdio.h>
#include <memory.h>
using namespace std;

const int MAXN = 205;
const int MAXE = 45000;
const int INF = 0x3fffffff;

int d[MAXE],v[MAXE],u[MAXE],low[MAXE],up[MAXE],pre[MAXE],c[MAXN][MAXN],num[MAXE];
int s,t,n,m;
void ini_d(int s,int t) {
  
  
   for(int i = 0; i < t+1; i++)
     d[i] = t+1,num[i] = 0;
   queue<int> q;
   num[0] = 1;
   d[t] = 0;
   q.push(t);
   int u;
   while(!q.empty()) {
      u = q.front();q.pop();
      for(int i = 0; i < t + 1; i++) {
         if(c[i][u] > 0 && d[i] >= t+1) {
            d[i] = d[u] + 1;
            num[d[i]]++;
            q.push(i);
         }
      }
   }
}

int findAlowArc(int i) {
   int j;
   for(j = 0; j < t + 1; j++) {
      if(c[i][j] > 0 && d[i] == d[j] + 1) return j;
   }
   return -1;
}

int reLable(int i) {
   int j;
   int mm = INF;
   for(j = 0; j < t + 1; j++) {
      if(c[i][j] > 0) mm = min(mm,d[j] + 1);
   }
   return mm == INF?t+1:mm;
}

int maxFlow(int s,int t) {
  
   ini_d(s,t);
   int flow = 0,i = s,j;
   int delta = INF;
   memset(pre,-1,sizeof(pre));
  
   while(d[s] < t+1) {
     
      j = findAlowArc(i);
      if(j >= 0) {
         pre[j] = i;
         i = j;
         if(i == t) {
            delta = INF;
            for(i = t; i != s; i = pre[i])
              delta = min(c[pre[i]][i],delta);
            for(i = t; i != s; i = pre[i]) {
               c[pre[i]][i] -= delta,c[i][pre[i]] += delta;
            }
            flow += delta;
         }
      }
      else {
        int x = reLable(i);
        num[x]++;
        num[d[i]]--;
        if(num[d[i]] == 0) return flow;
        d[i] = x;
        if(i != s) i = pre[i];
      }
   }
   return flow;
}
 
int main() {
  
   int cas;
   scanf("%d",&cas);
   while(cas--) {
      memset(c,0,sizeof(c));
      memset(low,0,sizeof(low));
      memset(up,0,sizeof(up));
     
      int sum = 0;
      scanf("%d%d",&n,&m);
      for(int i = 1; i <= m; i++) {
            scanf("%d%d%d%d",&u[i],&v[i],&low[i],&up[i]);
               c[u[i]][v[i]] += up[i] - low[i];
               c[0][v[i]] += low[i];
               c[u[i]][n+1] += low[i];
               sum += low[i];
         }
     
      s = 0,t = n+1;
      int ans = maxFlow(s,t);
      if(ans != sum) {
         puts("NO");
         continue;
      }
      puts("YES");
      for(int i = 1; i <= m; i++) {
          printf("%d\n",c[v[i]][u[i]] + low[i]);
      }
      
   }
  
   //system("pause");
   return 0;
}

   给出一个N个点和M条边的混合图，求出它的一条欧拉回路，如果没有，输出无解信息。
   无向边只能经过一次，所以不能把它拆成两条方向相反的有向边，而只能给每条无向边定向。有向图欧拉回路的有条性质是：当且仅当，图连通，并且每个节点的入度等于出度！！这题可以先给每条无向边定向，随意定。这样，每个节点现在大有可能出度不等于入度。如果一个点入度大于出度，那么让这s与这点相连，边容量为(出度-入度)/2;代表这个节点经过两次修改后能让出度等于入度。反之，连t节点。道理一样。如果是满流，那就对了，欧拉图。
  

   问题描述：给定正整数序列x1,x2,....，xn。要求
   1）计算最长递增子序列的长度s。
   2)计算从给定的序列中最多可取出多少长度为s的递增子序列。
   3）如果允许在去除的序列中多次使用x1和xn，则从给定序列中最多可取出长度为s的递增子序列。
   解题报告： 

首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。

1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。

2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。

3、如果F[i]=1，从<i.b>到T连接一条容量为1的有向边。

4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，从<i.b>到<j.a>连接一条容量为1的有向边。

求网络最大流，就是第二问的结果。把边(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。

上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。

  题目的意思是要求都多少边不重合的最短路。可以先用一个二重循环算出哪些边在可在最短路中，然后给他们赋值容量1，然后再从求个最大流就好了。下面给出计算哪些边在最短路径中的代码。

     摘要:   此题可以要求的是在满足每头牛能找到窝的情况下（也就最大流能满足等于n的时候），使得每头牛的对窝的排名中最大减去最小的值最小，听上去很拗口，但是明白了意思了就跟很多题都差不多的。就那么回事，这里采用二分枚举，但是每次删边的时候用两个参数，最大和最小的rank值，尽量让他们靠近，靠得越近就越小。条件就是最大流 == n；  #include <io...  阅读全文

  题目连接：http://poj.org/problem?id=3498
  带点容量限制的做法是拆点，把一个点拆成两个点，他们直接连一条边就是点容量。然后再求最大流。
  此题的做法是把每个ice floe拆成两个点i,和i'，他们之间连一条边为可跳跃次数，原点连接每个ice floe的i，容量为每个ice floe上企鹅的个数，然后根据企鹅的跳跃与坐标位置见图，如果企鹅可从i题floe i 跳到 floe j, 则i'向j连一条无穷大的边，j‘向i连一条无穷大的边，然后枚举汇点，建立一个汇点，然后用枚举的floe i和汇点连一条无穷大的边，这里要注意，不需要每次去重新见图，直接删除添加与汇点连接的那条边就好，邻接表不知道怎么完成删除一条边，用邻接矩阵就可以了。到此建模完成，直接流。代码就不贴了。

     摘要:    floyd + 二分 + sap 对于点权值的的最大流需要拆点构图，把权值边放到一个数组里面，进行排序，然后枚举答案，这题再怎么简化还是很长。 #include<iostream>#include<algorithm>using namespace std ;const int N =&...  阅读全文

     摘要: 题目意思是要求边有扩容之后能使流量加大，问这样的边有几条，这里要注意的是，最小割不一定就是这种边，但是这种边就一定是割了，因为假设可能有一条增光路上有和最小割相同容量的边，那么扩容了最小割也没用，所以一次DFS正向反向都不行，必须两次DFS。正的来一次，反向图从汇点来一次，标记1,2然后连接1和2的那条边就是可扩容边。假设x-.y是可扩容边，那么必定有，s->x和y->t存在。 【题...  阅读全文

     摘要: 最小点权覆盖，参考胡伯涛论文，这里是要求成本的乘积，所以先用log函数改成加法形式。 #include <iostream>#include <cmath>using namespace std;const double INF = 1e7;const int MAXN&n...  阅读全文