beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

康托展开的应用实例  {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是第三个大数。

posted @ 2011-03-22 08:33 成幸毅 阅读(255) | 评论 (0)编辑 收藏

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

#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;
}

posted @ 2010-10-26 09:25 成幸毅 阅读(261) | 评论 (0)编辑 收藏

   给出一个N个点和M条边的混合图,求出它的一条欧拉回路,如果没有,输出无解信息。
   无向边只能经过一次,所以不能把它拆成两条方向相反的有向边,而只能给每条无向边定向。有向图欧拉回路的有条性质是:当且仅当,图连通,并且每个节点的入度等于出度!!这题可以先给每条无向边定向,随意定。这样,每个节点现在大有可能出度不等于入度。如果一个点入度大于出度,那么让这s与这点相连,边容量为(出度-入度)/2;代表这个节点经过两次修改后能让出度等于入度。反之,连t节点。道理一样。如果是满流,那就对了,欧拉图。
  
int main() {
   
int cas;
   scanf(
"%d",&cas);
   
while(cas--{
      memset(degree,
0,sizeof(degree));
      memset(head,
-1,sizeof(head));
      sps 
= 0;
      
int sum = 0;
      scanf(
"%d%d",&n,&m);
      
for(int i = 0; i < m; i++{
         scanf(
"%d%d%d",&vex1[i],&vex2[i],&dir[i]);
         degree[vex1[i]]
++;
         degree[vex2[i]]
--;
      }

        
int i;
       
for( i = 1; i <= n; i++{
           
if(abs(degree[i])&1)
              
break;
       }

       
if(i <= n)  {
            printf(
"impossible\n"); continue;
       }


      s 
= 0,t = n+1;
      NN 
= t+1;
      
for(int i = 0; i < m; i++{
         
if(!dir[i] && vex1[i] != vex2[i])
            addedge(vex1[i],vex2[i],
1);
      }

      
for(int i = 1; i <= n;i++{
         
if(degree[i] > 0{
            addedge(s,i,(degree[i])
/2);
            sum 
+= degree[i]/2;
         }

         
         
else if(degree[i] < 0{
            addedge(i,t,
-degree[i]/2);
         }

      }

         
if(maxFlow(s,t) == sum) {
            printf(
"possible\n");
         }

         
else 
            printf(
"impossible\n");
   }

  
// system("pause");
   return 0;
}

posted @ 2010-10-14 20:07 成幸毅 阅读(455) | 评论 (0)编辑 收藏

   问题描述:给定正整数序列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>iA[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的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出,需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数,所以最大流量就是第二问结果。第三问特殊地要求x1xn可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可。

posted @ 2010-10-08 22:16 成幸毅 阅读(1491) | 评论 (2)编辑 收藏

  题目的意思是要求都多少边不重合的最短路。可以先用一个二重循环算出哪些边在可在最短路中,然后给他们赋值容量1,然后再从求个最大流就好了。下面给出计算哪些边在最短路径中的代码。
void floyd() {
   
   
for(int k = 0; k < n; k++
      
for(int i = 0; i < n; i++
         
if(d[i][k] != INF ) 
            
for(int j = 0; j < n; j++{
               
if(d[k][j] != INF) {
                   
if(d[i][j] > d[k][j] + d[i][k]) {
                      d[i][j] 
= d[k][j] + d[i][k];
                   }
 
               }

            }

   
   
for(int i = 0; i < n; i++)
      
if(d[s][i] != INF)
         
for(int j = 0; j < n; j++{
           
if(d[j][t] != INF)
            
if(mat[i][j] != -1 ){
               
if(d[s][t] == d[s][i] + mat[i][j] + d[j][t]) {
                 c[i][j] 
= 1;
               }

            }

         }
 
    
}
 

posted @ 2010-10-08 22:09 成幸毅 阅读(352) | 评论 (0)编辑 收藏

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

posted @ 2010-10-07 18:57 成幸毅 阅读(334) | 评论 (0)编辑 收藏

  题目连接: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和汇点连一条无穷大的边,这里要注意,不需要每次去重新见图,直接删除添加与汇点连接的那条边就好,邻接表不知道怎么完成删除一条边,用邻接矩阵就可以了。到此建模完成,直接流。代码就不贴了。

posted @ 2010-10-07 18:50 成幸毅 阅读(525) | 评论 (0)编辑 收藏

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

posted @ 2010-10-06 19:25 成幸毅 阅读(291) | 评论 (0)编辑 收藏

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

posted @ 2010-10-06 11:53 成幸毅 阅读(308) | 评论 (0)编辑 收藏

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

posted @ 2010-10-06 11:40 成幸毅 阅读(392) | 评论 (0)编辑 收藏

仅列出标题
共3页: 1 2 3