C++博客-O(1) 的小乐 http://www.cppblog.com/sosi/Job Huntingzh-cnMon, 20 Apr 2026 03:16:16 GMTMon, 20 Apr 2026 03:16:16 GMT60算法设计4——贪心算法(3)http://www.cppblog.com/sosi/archive/2012/11/15/195236.htmlSosiSosiThu, 15 Nov 2012 08:38:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/15/195236.htmlhttp://www.cppblog.com/sosi/comments/195236.htmlhttp://www.cppblog.com/sosi/archive/2012/11/15/195236.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/195236.htmlhttp://www.cppblog.com/sosi/services/trackbacks/195236.html1 聚类问题：最大间隔的K聚类。我们定义一个K聚类的间隔是处在不同聚类中的任意一对点之间的最小距离。一个自然的目标是寻求具有最大可能间隔的k聚类。

这个问题的算法与Kruskal算法非常相似，首先每一个点都是一个聚类，然后依次按照Kruskal进行计算。。。相当于在Kruskal中删除了k-1条最贵的边。

2  假设给定一个连通图G，假定边的费用都是不同的，G有n个顶点和m条边，指定了G的一条特定的边e，给出一个运行时间在O(m+n)的算法来确定e是否包含在G的一棵最小生成树里。

算法现在就已经很显然了，我们通过从G中删除所有权比e大的边，（包括e）然后使用看一下e中的两个端的是否联通。当前仅当没有这样一条路径的时候，e属于一棵最小生成树。

3 看一下最小生成树的两个性质： 

割性质：当e是从某个集合S跨到补集V-S的最便宜的边，那么它在每一颗最小生成树里。

圈性质：如果e是某个圈C上最贵的边，那么它不在最小生成树里。

4 一个课后问题：

给定一个最短路问题，但是边权是一个到达时间的函数(边权统一为时间的量纲， 函数单调递增)，此时仍然是Dijkstra算法，Dijkstra 算法实质就是一个宽度优先搜索。

QQ截图20121115145333

5 给定一棵完全二叉树，然后每个边有权值。要求修改边，然后使得跟到每个叶子节点的距离相同，要求修改的和最小？给出一个算法，这个在电路设计中就是同时性的要求。

这个是个非常不错的算法。还是一个递归的过程：

T0G6CYQEEWAT$ZESUY3J(L6

6 

  给定一个连通图，他的边的费用都是不同的，证明G有唯一的一棵最小生成树。

如果G有两棵最小生成树，则T 和P，必然有不同的边，把T与P不同的边加入到P中，必然形成圈。



Sosi 2012-11-15 16:38 发表评论
]]>Timus 1078 SPFAhttp://www.cppblog.com/sosi/archive/2012/11/10/195013.htmlSosiSosiSat, 10 Nov 2012 06:39:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/10/195013.htmlhttp://www.cppblog.com/sosi/comments/195013.htmlhttp://www.cppblog.com/sosi/archive/2012/11/10/195013.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/195013.htmlhttp://www.cppblog.com/sosi/services/trackbacks/195013.html之前做这个题使用的方法是Floyd其所有点的最长路，但是这个还可以使用SPFA来做，因为这个图是肯定没有正环的图，然后把所有入读为0的点，都一次性的加入到SPFA的队列或者栈中，则可以求解出一个全局最大值。然后用SPFA可以加一个父亲域，来回复我们获得的路径。

 

   1:   
   2:  #include <queue>
   3:  #include <iostream>
   4:  #include <string.h>
   5:  #include <stdio.h>
   6:  #include <algorithm>
   7:  #include <vector>
   8:  using namespace std;
   9:  #define V 30010      // vertex
  10:  #define E 150010      // edge
  11:  #define INF 0x3F3F3F3F
  12:   
  13:  struct node
  14:  {
  15:      int v, w, next;
  16:  }pnt[E];
  17:   
  18:  int head[V];
  19:  int  dis[V];
  20:  bool vis[V];
  21:  int  cnt[V];          // the num of the operation of push to Quque. negatvie cycle.
  22:  int e = 0;            // the index of the edge
  23:  int N ;               // the num of the vertex.
  24:  int M ;               // the num of edges
  25:  int src, sink;
  26:  int father[V];
  27:  int ru[V];
  28:  void addedge(int  u, int v, int w)
  29:  {
  30:      pnt[e].v = v; pnt[e].w= w;
  31:      pnt[e].next = head[u]; head[u] = e++;
  32:  }
  33:  void SPFA_init()
  34:  {
  35:      e=0;
  36:      memset(head, -1,sizeof(head));
  37:      memset(vis, 0 ,sizeof(vis));
  38:      memset(cnt, 0 ,sizeof(cnt));
  39:      for(int i=0; i<=N; i++) dis[i] = -1;          // MODIFIED
  40:      memset(father, -1, sizeof(father));
  41:  }
  42:  int SPFA()
  43:  {
  44:      queue<int> Q;
  45:      for(int i=1; i<=N; i++) 
  46:      {
  47:          src = i;
  48:          if(ru[i] == 0)
  49:          {
  50:              Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src];
  51:          }
  52:      }
  53:      while(!Q.empty()) 
  54:      {
  55:          int u = Q.front(); Q.pop();  vis[u] = 0;
  56:          for(int i=head[u]; i!=-1; i=pnt[i].next)
  57:          {
  58:              int v = pnt[i].v;
  59:              if( dis[v] < dis[u] + pnt[i].w  )          // MODIFIED
  60:              {
  61:                  dis[v] = dis[u] + pnt[i].w;
  62:                  father[v] = u;
  63:                  if(!vis[v]) { Q.push(v); vis[v] = 1;}
  64:                  if( ++cnt[v] > N) return -1;   // positive  cycle.
  65:              }
  66:          }
  67:      }
  68:      if(dis[sink] == -1 ) return -2;            // can't from src to sink. 
  69:      return dis[sink];
  70:  }
  71:   
  72:  int main()
  73:  {
  74:      //freopen("1078.txt","r",stdin);
  75:      scanf("%d", &N);
  76:      int a, b;
  77:      vector<pair<int, int> > C;
  78:      memset(ru, 0 ,sizeof(ru));
  79:      SPFA_init();
  80:      for(int i=0; i<N; i++)
  81:      {
  82:          int a, b;
  83:          scanf("%d%d", &a, &b);
  84:          C.push_back(make_pair(a,b));
  85:          for(int i=0; i<C.size(); i++)
  86:          {
  87:              if(a<C[i].first && b> C[i].second)
  88:              {
  89:                  ru[C.size()]++;
  90:                  addedge(i+1,C.size() , 1);
  91:              }
  92:              else if(a> C[i].first && b< C[i].second)
  93:              {
  94:                  ru[i+1]++;
  95:                  addedge(C.size(), i+1,1);
  96:              }
  97:          }
  98:      }
  99:      SPFA();
 100:      //for(int i=1; i<=N; i++) cout<<father[i]<<" "; cout<<endl;
 101:      int ret  =0; int idx = -1;
 102:      for(int i=1; i<=N; i++)
 103:      {
 104:          if(dis[i]>ret)
 105:          {
 106:              ret = dis[i];
 107:              idx = i;
 108:          }
 109:      }
 110:      if(ret == 0)
 111:      {
 112:          cout<<1<<endl;
 113:          cout<<1<<endl;
 114:      }
 115:      else
 116:      {
 117:          cout<<ret+1<<endl;
 118:          vector<int> D;
 119:          D.push_back(idx);
 120:          while(father[idx] != -1)
 121:          {
 122:              D.push_back(father[idx]);
 123:              idx = father[idx];
 124:          }
 125:          reverse(D.begin(), D.end());
 126:          for(int i=0; i<D.size(); i++) cout<<D[i]<<" ";
 127:          cout<<endl;
 128:      }
 129:      return 0;
 130:  }


Sosi 2012-11-10 14:39 发表评论
]]>Timus 1078 最长路Floydhttp://www.cppblog.com/sosi/archive/2012/11/10/195008.htmlSosiSosiSat, 10 Nov 2012 04:50:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/10/195008.htmlhttp://www.cppblog.com/sosi/comments/195008.htmlhttp://www.cppblog.com/sosi/archive/2012/11/10/195008.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/195008.htmlhttp://www.cppblog.com/sosi/services/trackbacks/195008.html可以把问题转换为一个有向图中求最长路的过程，需要Floyd算法来打印最长路。保存即可。

http://acm.timus.ru/problem.aspx?space=1&num=1078

 

   1:   
   2:  #include <queue>
   3:  #include <iostream>
   4:  #include <string.h>
   5:  #include <stdio.h>
   6:  using namespace std;
   7:  #define V 505      // vertex
   8:  #define INF 0x3F3F3F3F
   9:  int N; 
  10:  int dis[V][V];
  11:  int path[V][V];
  12:   
  13:  // normal distance.
  14:  void floyd()
  15:  {
  16:      for(int k=1;k<=N;k++)
  17:      {
  18:          for(int i=1;i<=N;i++)
  19:          {
  20:              for(int j=1;j<=N;j++)
  21:              {
  22:                  if(dis[i][k]== -INF || dis[k][j] == -INF) continue;
  23:                  if(dis[i][k] + dis[k][j] > dis[i][j])
  24:                  {
  25:                      dis[i][j] = dis[i][k] + dis[k][j];
  26:                      path[i][j] = path[i][k];
  27:                  }
  28:   
  29:              }
  30:          }
  31:      }
  32:  }
  33:  void floyd_path(int i, int j)
  34:  {
  35:      int k=path[i][j];
  36:      while(k!=j)
  37:      {
  38:          printf(" %d", k );
  39:          k= path[k][j];
  40:      }
  41:  }
  42:   
  43:  int main()
  44:  {
  45:      //freopen("1078.txt","r",stdin);
  46:      scanf("%d", &N);
  47:      int a, b;
  48:      vector<pair<int, int> > C;
  49:      memset(dis, 0 ,sizeof(dis));
  50:      for(int i=0; i<N; i++)
  51:      {
  52:          scanf("%d%d", &a, &b);
  53:          C.push_back(make_pair(a,b));
  54:          for(int i=0; i<C.size(); i++)
  55:          {
  56:              if(a<C[i].first && b> C[i].second)
  57:              {
  58:                  dis[i+1][C.size()] = 1;
  59:                  path[i+1][C.size()] = C.size();
  60:              }
  61:              else if(a> C[i].first && b< C[i].second)
  62:              {
  63:                  dis[C.size()][i+1]=1;
  64:                  path[C.size()][i+1] = i+1;
  65:              }
  66:          }
  67:      }
  68:      for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(dis[i][j]==0) dis[i][j]=-INF;
  69:      floyd();
  70:      int ret = 0;
  71:      for(int i=1; i<=N; i++)
  72:      {
  73:          for(int j=1; j<=N; j++)
  74:          {
  75:              if(dis[i][j] > ret)
  76:              {
  77:                  ret = dis[i][j];
  78:                  a = i; b = j;
  79:              }
  80:          }
  81:      }
  82:      if(ret == 0) 
  83:      {
  84:          cout<<1<<endl;
  85:          cout<<1<<endl;
  86:      }else
  87:      {
  88:          cout<<ret+1<<endl;
  89:          cout<<a;
  90:          floyd_path(a,b);
  91:          cout<<" "<<b<<endl;
  92:      }
  93:      return 0;
  94:  }
  95:   


Sosi 2012-11-10 12:50 发表评论
]]>POJ 3268http://www.cppblog.com/sosi/archive/2012/11/10/194999.htmlSosiSosiFri, 09 Nov 2012 16:03:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/10/194999.htmlhttp://www.cppblog.com/sosi/comments/194999.htmlhttp://www.cppblog.com/sosi/archive/2012/11/10/194999.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/194999.htmlhttp://www.cppblog.com/sosi/services/trackbacks/194999.html求从原点到达某个点之后返回，来回最长的距离是多少？ 比较基础的问题，两遍Dijkstra就可以了。

   1:   
   2:  #include <iostream> 
   3:  #include <vector>
   4:  #include <algorithm>
   5:  #include <queue>
   6:  #include <string.h>
   7:  #include <stdio.h>
   8:  using namespace std;
   9:   
  10:  #define V   1005
  11:  #define E   100005
  12:  #define INF 329999         
  13:   
  14:  // v :the end point of an edge. w : the weight of the weight next:cluster according to the begin point of the edge
  15:  struct node
  16:  {
  17:      int v, w,next;
  18:      node(int vv=0, int ww=0):v(vv),w(ww){}
  19:      bool operator < (const node& r) const{return w> r.w;}
  20:  }pnt[E],pnt1[E];
  21:   
  22:  int e=0,N,M,s;
  23:   
  24:  int head[V];
  25:  int dis[V];
  26:  bool vis[V];
  27:  int src, sink;
  28:   
  29:  void Dijkstra()
  30:  { 
  31:      priority_queue<node> Q; 
  32:      vis[src] = 1; dis[src] = 0; 
  33:      Q.push(node(src, 0)); 
  34:      for (int u = src, i=1; i< N; i++)                 
  35:      { 
  36:          for (int j = head[u]; j != -1; j = pnt[j].next)    // j is edge number.
  37:          { 
  38:              int v = pnt[j].v;                          
  39:              if (vis[v] == 0 && dis[v] > dis[u] + pnt[j].w )// pre is the current vertex
  40:              { 
  41:                  dis[v] = dis[u] + pnt[j].w; 
  42:                  Q.push(node(v, dis[v]));
  43:              } 
  44:          } 
  45:          while (!Q.empty() && vis[Q.top().v]) Q.pop(); 
  46:          if (Q.empty()) break;
  47:          vis[u = Q.top().v] = 1; Q.pop();
  48:      }
  49:  } 
  50:  int head1[V];
  51:  inline void addedge1(int u, int v, int w)
  52:  {
  53:      pnt1[s].v =v; pnt1[s].w = w; pnt1[s].next = head1[u]; head1[u]=s++;
  54:  }
  55:  inline void addedge(int u, int v, int w){ 
  56:      pnt[e].v = v; pnt[e].w = w; pnt[e].next= head[u]; head[u]=e++;
  57:  } 
  58:   
  59:  void Dijkstra_init()
  60:  { 
  61:      e = 0; s =0;
  62:      memset(head, -1, sizeof(head)); 
  63:      memset(head1, -1, sizeof(head));
  64:      memset(vis, 0, sizeof(vis));
  65:      scanf("%d%d", &N , &M);
  66:      for (int i = 0; i <=N; i++) dis[i] = INF; 
  67:      scanf("%d", &src);
  68:      //cout<<src<<endl;
  69:      for(int i=0; i<M; i++)
  70:      {
  71:          int a, b, c;
  72:          scanf("%d%d%d", &a, &b, &c);
  73:          addedge(a, b, c);
  74:          addedge1(b,a, c);
  75:      }
  76:   
  77:   
  78:  } 
  79:   
  80:  int main()
  81:  {
  82:      //freopen("3268.txt","r",stdin);
  83:   
  84:      Dijkstra_init();
  85:      Dijkstra();
  86:      int dis1[V];
  87:      for(int i=0; i<=N; i++) dis1[i] = dis[i];
  88:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
  89:      memset(vis, 0 ,sizeof(vis));
  90:      for(int i=0; i<=N; i++) { dis[i]= INF; head[i] = head1[i];}
  91:      for(int i=0; i<M; i++)
  92:      {
  93:          pnt[i]=pnt1[i];
  94:   
  95:      }
  96:      Dijkstra();
  97:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
  98:      int ret = 0;
  99:      for(int i=1; i<=N; i++) ret = max(ret, dis1[i]+dis[i]);
 100:      cout<<ret<<endl;
 101:      return 0;
 102:  }
 103:   


Sosi 2012-11-10 00:03 发表评论
]]>POJ 1860 SPFA 最长路http://www.cppblog.com/sosi/archive/2012/11/09/194997.htmlSosiSosiFri, 09 Nov 2012 15:24:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/09/194997.htmlhttp://www.cppblog.com/sosi/comments/194997.htmlhttp://www.cppblog.com/sosi/archive/2012/11/09/194997.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/194997.htmlhttp://www.cppblog.com/sosi/services/trackbacks/194997.html货币兑换问题，经典问题，这个问题解决的关键是发现，如果存在正环，那么一定是YES。稍微改一下SPFA，寻找一个图中的正环。

 

   1:  /**
   2:  search the longest path , just jude whether there are a positve cycle.
   3:  
   4:  */
   5:   
   6:  #include <queue>
   7:  #include <iostream>
   8:  #include <string.h>
   9:  #include <stdio.h>
  10:  using namespace std;
  11:  #define V 3000      // vertex
  12:  #define E 1500      // edge
  13:  #define INF 1000000.0f
  14:   
  15:  struct node
  16:  {
  17:      int v, next;
  18:      double R,C,w;
  19:  }pnt[E];
  20:   
  21:  int head[V];
  22:  double  dis[V];
  23:  bool vis[V];
  24:  int  cnt[V];          // the num of the operation of push to Quque. negatvie cycle.
  25:  int e = 0;            // the index of the edge
  26:  int N ;               // the num of the vertex.
  27:  int M ;               // the num of edges
  28:  int src, sink;
  29:  double val;
  30:  void addedge(int  u, int v, double R, double C)
  31:  {
  32:      pnt[e].v = v; pnt[e].w= 0;
  33:      pnt[e].R = R; pnt[e].C = C;
  34:      pnt[e].next = head[u]; head[u] = e++;
  35:  }
  36:  void SPFA_init()
  37:  {
  38:      e=0;
  39:      memset(head, -1,sizeof(head));
  40:      memset(vis, 0 ,sizeof(vis));
  41:      memset(cnt, 0 ,sizeof(cnt));
  42:      for(int i=0; i<=N; i++) dis[i] = 0;
  43:  }
  44:  int SPFA()
  45:  {
  46:      queue<int> Q;
  47:      Q.push(src); vis[src] = 1; dis[src] = val; ++cnt[src]; 
  48:      while(!Q.empty()) 
  49:      {
  50:          int u = Q.front(); Q.pop();  vis[u] = 0;
  51:          for(int i=head[u]; i!=-1; i=pnt[i].next)
  52:          {
  53:              int v = pnt[i].v;
  54:              pnt[i].w = (dis[u] - pnt[i].C)*pnt[i].R - dis[u];
  55:              //cout<<u<<" to "<<v<<" "<<pnt[i].w<<endl;
  56:              if( dis[v] < dis[u] + pnt[i].w  )
  57:              {
  58:                  dis[v] = dis[u] + pnt[i].w;
  59:                  //cout<<u<<" to "<<v<<"  "<<pnt[i].w<<" "<<dis[v]<<endl;
  60:                  if(!vis[v]) { Q.push(v); vis[v] = 1;}
  61:                  if( ++cnt[v] > N) return -1; // negative cycle.
  62:              }
  63:          }
  64:      }
  65:      return 1;
  66:      //if(dis[sink] == INF) return -2;          // can't from src to sink. 
  67:      //return dis[sink];
  68:  }
  69:   
  70:  int main()
  71:  {
  72:      freopen("1860.txt","r",stdin);
  73:      scanf("%d%d", &N , &M);
  74:   
  75:      scanf("%d", &src);
  76:      //cout<<src<<endl;
  77:      scanf("%lf", &val);
  78:      //cout<<val<<endl;
  79:      SPFA_init();
  80:      for(int i=0; i<M; i++)
  81:      {
  82:          int a, b; double Rab, Cab, Rba,Cba;
  83:          scanf("%d%d", &a, &b);
  84:          scanf("%lf%lf", &Rab, &Cab);
  85:          scanf("%lf%lf", &Rba, &Cba);
  86:          addedge(a, b,Rab, Cab);
  87:          addedge(b,a,Rba, Cba);
  88:          //cout<<Rab<<" "<<Cab<<" "<<Rba<<" "<<Cba<<endl;
  89:      }
  90:      int ret = SPFA();
  91:      if(ret == -1)  cout<<"YES"<<endl;
  92:      else cout<<"NO"<<endl;
  93:      return 0;
  94:  }


Sosi 2012-11-09 23:24 发表评论
]]>POJ 3169 差分约束方程http://www.cppblog.com/sosi/archive/2012/11/09/194994.htmlSosiSosiFri, 09 Nov 2012 13:38:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/09/194994.htmlhttp://www.cppblog.com/sosi/comments/194994.htmlhttp://www.cppblog.com/sosi/archive/2012/11/09/194994.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/194994.htmlhttp://www.cppblog.com/sosi/services/trackbacks/194994.html一道简单的差分约束方程，差分约束方程由Bellmanford转换而来，一组差分方程由 x-y <=d 的形式，而在最短路中松弛条件有dis(x)<= dis(y)+w。 所以产生了一条由y连向x的有向边，权重为d。

https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3169.cpp

   1:   
   2:  #include <queue>
   3:  #include <iostream>
   4:  #include <string.h>
   5:  #include <stdio.h>
   6:  using namespace std;
   7:  #define MAXN 1005      // vertex
   8:  #define MAXM 20005      // edge
   9:  #define INF 0x3F3F3F3F
  10:   
  11:  struct node
  12:  {
  13:      int v, w, next;
  14:  }pnt[MAXM];
  15:   
  16:  int head[MAXN];
  17:  int  dis[MAXN];
  18:  bool vis[MAXN];
  19:  int  cnt[MAXN];       // the number of the operation of push to Quque. negatvie cycle.
  20:  int num = 0;          // the index of the edge
  21:  int N ;               // the number of the vertex.
  22:  int M ;               // the number of edges
  23:  int src, sink;
  24:  void addedge(int  u, int v, int w)
  25:  {
  26:      pnt[num].v = v; pnt[num].w= w;
  27:      pnt[num].next = head[u]; head[u] = num++;
  28:  }
  29:   
  30:  int SPFA()
  31:  {
  32:      for(int i=0; i<=N; i++)
  33:      {
  34:          vis[i]=0; dis[i] = INF; cnt[i] = 0;
  35:      }
  36:   
  37:      queue<int> Q;
  38:      Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src]; 
  39:      while(!Q.empty()) 
  40:      {
  41:          int u = Q.front(); Q.pop();  vis[u] = 0;
  42:          for(int i=head[u]; i!=-1; i=pnt[i].next)
  43:          {
  44:              int v = pnt[i].v;
  45:              if( dis[v] > dis[u] + pnt[i].w  )
  46:              {
  47:                  dis[v] = dis[u] + pnt[i].w;
  48:                  if(!vis[v]) {Q.push(v); vis[v] = 1;}
  49:                  if( ++cnt[v] > N) return -1; // negative cycle.
  50:              }
  51:          }
  52:      }
  53:      if(dis[sink] == INF) return -2; // can't from src to sink.
  54:      return dis[sink];
  55:  }
  56:   
  57:  int main()
  58:  {
  59:      int ml,md;
  60:      while(scanf("%d%d%d", &N , &ml, &md)!= EOF)
  61:      {
  62:          num = 0;
  63:          memset(head, -1, sizeof(head)); 
  64:          int a, b, c;
  65:          for(int i=0; i<ml; i++)
  66:          {
  67:              scanf("%d%d%d", &a, &b, &c);
  68:              if(a>b) swap(a,b);
  69:              addedge(a, b,c);
  70:          }
  71:          for(int i=0; i<md; i++)
  72:          {
  73:              scanf("%d%d%d", &a, &b, &c);
  74:              if(a<b) swap(a,b);
  75:              addedge(a, b, -c);
  76:          }
  77:          src = 1; sink = N;
  78:          printf("%d\n", SPFA());
  79:      }
  80:      return 0;
  81:  }
.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

Sosi 2012-11-09 21:38 发表评论
]]>POJ 3159 SPFAhttp://www.cppblog.com/sosi/archive/2012/11/09/194992.htmlSosiSosiFri, 09 Nov 2012 13:15:00 GMThttp://www.cppblog.com/sosi/archive/2012/11/09/194992.htmlhttp://www.cppblog.com/sosi/comments/194992.htmlhttp://www.cppblog.com/sosi/archive/2012/11/09/194992.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/194992.htmlhttp://www.cppblog.com/sosi/services/trackbacks/194992.html给定一个图，（V  3*10^4， E 1.5*10^5）,如此大规模的图，求一个最短路，只能使用SPFA（使用栈进行优化）

https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3159.cpp

   1:  #include <queue>
   2:  #include <iostream>
   3:  #include <string.h>
   4:  #include <stdio.h>
   5:  using namespace std;
   6:  #define MAXN 30010      // vertex
   7:  #define MAXM 150010      // edge
   8:  #define INF 0x3F3F3F3F
   9:   
  10:  struct node
  11:  {
  12:      int v, w, next;
  13:  }pnt[MAXM];
  14:   
  15:  int head[MAXN];
  16:  int  dis[MAXN];
  17:  bool vis[MAXN];
  18:  int  cnt[MAXN];       // the number of the operation of push to Quque. negatvie cycle.
  19:  int num = 0;          // the index of the edge
  20:  int N ;               // the number of the vertex.
  21:  int M ;               // the number of edges
  22:  int src, sink;
  23:  void addedge(int  u, int v, int w)
  24:  {
  25:      pnt[num].v = v; pnt[num].w= w;
  26:      pnt[num].next = head[u]; head[u] = num++;
  27:  }
  28:   
  29:  int SPFA()
  30:  {
  31:      for(int i=0; i<=N; i++)
  32:      {
  33:          vis[i]=0; dis[i] = INF; cnt[i] = 0;
  34:      }
  35:   
  36:      int Q[MAXM], top=1;
  37:      Q[0] = src; vis[src] = 1;
  38:      dis[src] = 0;
  39:      while(top)
  40:      {
  41:          int u = Q[--top]; vis[u] = 0;
  42:          for(int i = head[u]; i!=-1; i=pnt[i].next)
  43:          {
  44:              int v = pnt[i].v;
  45:              if(dis[v]> dis[u] + pnt[i].w )
  46:              {
  47:                  dis[v]= dis[u] +pnt[i].w;
  48:                  if(!vis[v])
  49:                  {
  50:                      Q[top++] = v; vis[v]= 1;
  51:                  }
  52:              }
  53:   
  54:          }
  55:      }
  56:   
  57:   
  58:   
  59:      return dis[sink];
  60:  }
  61:   
  62:  int main()
  63:  {
  64:      //freopen("3159.txt", "r", stdin);
  65:      while(scanf("%d%d", &N , &M)!= EOF)
  66:      {
  67:          num = 0;
  68:          memset(head, -1, sizeof(head)); 
  69:          for(int i=0; i<M; i++)
  70:          {
  71:              int a, b, c;
  72:              scanf("%d%d%d", &a, &b, &c);
  73:              addedge(a, b,c);
  74:          }
  75:          //cout<<num<<endl;
  76:          src = 1; sink = N;
  77:          //cout<<"src "<<src<<" sink "<<N<<endl;
  78:          printf("%d\n", SPFA());
  79:      }
  80:      return 0;
  81:  }


Sosi 2012-11-09 21:15 发表评论
]]>算法设计5——分治策略 （1）http://www.cppblog.com/sosi/archive/2012/10/26/193894.htmlSosiSosiFri, 26 Oct 2012 03:41:00 GMThttp://www.cppblog.com/sosi/archive/2012/10/26/193894.htmlhttp://www.cppblog.com/sosi/comments/193894.htmlhttp://www.cppblog.com/sosi/archive/2012/10/26/193894.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/193894.htmlhttp://www.cppblog.com/sosi/services/trackbacks/193894.html1 对于分治策略中，分解容易合成较为复杂的情况，往往都需要子集有序这样一个条件。

2 分析递归式的方法一般都是看主定理，主定理其实只需要记住一点就OK，logba.

QQ截图20121026111232

如果不记得主定理，那么就需要分析递归式。

    求解递归式的最直接的方法是按照最初几级的运行时间展开递归式，找出当递归式展开时继续进行的模式。然后在递归的所有级上求和，从而得到总的运行时间。

    求解递归式的第二个方法是一开始对解有一个猜想，把它代入递推关系，检查其是否正确。

3 平面几何中找最近邻点对的问题，首先是对平面内所有点按照x坐标排序(很多的平面几何问题，为了降低复杂度都需要排序，后面看到一个MIT的题目，也需要对点进行极角排序)。然后分治，最后问题的关键是合并，取两个子问题中的最短距离作为/theta 中间带的衡量标准。因为要求中间带的可能的更短距离，所以所有点考虑的相邻格子数有限，且每个格子只能有一个点。

我觉得上面那个Merge那一步是整个算法的最核心和最关键的地方！！

4 大整数乘法问题，给出了一个递归的方案。X*Y，把x分为前后两部分，Y分为前后两部分，交叉相乘的部分改成了一个(xh+xl)*(yh+yl)-xhyh-xlyl的过程。递归变成了 T(n)<= 3T(2/n)+cn .矩阵乘法问题也是类似的一个技巧。大多停留在理论阶段。

下面是几个练习题：

1 MIT的一个练习题：

平面内给2N个点，无三点共线，分为两类，一类是红点（N个），一类是绿点(N个)。给出一个红点和绿点的连线方案，要求连线线段互不相交。算法复杂度O(n^2logn)

首先O(nlogn)找出分类面，分类面两边红点绿点个数分别相等。方法是首先极角排序，如果极点是红点，从小到大找到第一个绿点个数大于红点个数的点。连线即为分界面。递归解决两个子问题。

最坏情况是一个子问题退化为空，此时复杂度为O(n^2logn).

2 给N个数据，是一个单峰函数。O(logn)时间内求此单峰函数的极值。

每一次探查，探查3个点。然后二分找。

3 求N个数的逆序对问题，只不过变形为i<j  ai>2*aj 才认为是逆序对。这个问题有一个陷阱。就是要进行两遍Merge，第一遍是求逆序对。第二遍是排序合并。  这个一定要想清楚啊！！

4 有一组N张卡，求一个方法来探测是否有大于N/2张卡等价。操作只有一种，即比较两张卡是否等价。

QQ截图20121026113419

5 给一个N*N的4连通网格图，O(n)时间内确定找到一个局部极小值。

QQ截图20121026113656

思想就是先探测最外圈，然后探测次外圈，然后找中间两条分割线，再找分成的四个小区域的最外圈。可以找到一个局部极小值。



Sosi 2012-10-26 11:41 发表评论
]]>一道网易游戏笔试题http://www.cppblog.com/sosi/archive/2012/10/23/193719.htmlSosiSosiTue, 23 Oct 2012 03:39:00 GMThttp://www.cppblog.com/sosi/archive/2012/10/23/193719.htmlhttp://www.cppblog.com/sosi/comments/193719.htmlhttp://www.cppblog.com/sosi/archive/2012/10/23/193719.html#Feedback5http://www.cppblog.com/sosi/comments/commentRss/193719.htmlhttp://www.cppblog.com/sosi/services/trackbacks/193719.html题目：英雄升级，从0级升到1级，概率100%。

从1级升到2级，有1/3的可能成功；1/3的可能停留原级；1/3的可能下降到0级；
从2级升到3级，有1/9的可能成功；4/9的可能停留原级；4/9的可能下降到1级。
每次升级要花费一个宝石，不管成功还是停留还是降级。
求英雄从0级升到3级平均花费的宝石数目。

这个题目秒杀了一大片，一开始看到这个题目，立刻反应出来的是自动机DP，然后就朝着自动机DP去想，很快一个公式就可以搞出来。

dp[i][k]表示k步之后在i级的概率。

dp[0][k] = 1/3*dp[1][k-1];

dp[1][k] = dp[0][k-1]+1/3*dp[1][k-1] + 4/9*dp[2][k-1]

dp[2][k] = 1/3*dp[1][k-1] + 4/9* dp[2][k-1];

dp[3][k]= 1/9*dp[2][k-1];

然后此递推式可以写成矩阵乘法的形式，最后的结果就是求/Sigma (k+1)/9*dp[2][k]; 这个矩阵可以转换为对角阵，然后可以求出其通项公式等等。。。其实这个问题是线性差分方程组的解法。。。还要求特征值 + Jordan标准型bulalalalala。。。。我觉得要算出一个解析解的话果断是跪了。。。用Matlab跑了一下：

A =

       0              1/3            0      

       1              1/3            4/9    

       0              1/3            4/9 

>> ret =0;

>> for k=1:1000

ret = ret+ (k+1)/9*[0 0 1]*A^k*[1 0 0]';

end

>> ret

ret =

      30 

竟然是整数30.。。被赤果果得鄙视智商了。。。

蛋疼的用C++再跑一遍：

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

double dp[4];
double nextdp[4];
int main()
{
    for(int i=0; i<4; i++) dp[i]=0.0f;
    dp[0]=1.0f;
    double ret=0.0f;
    for(int i=0; i<100000000; i++)
    {
        for(int j=0; j<4; j++) nextdp[j]=0.0f;
        nextdp[0]= 1/3.0*dp[1];
        nextdp[1]=1/3.0*dp[1]+dp[0]+4/9.0*dp[2];
        nextdp[2]=4/9.0*dp[2]+1/3.0*dp[1];
        nextdp[3]=1/9.0*dp[2];
        ret+=i*dp[3];
        for(int j=0; j<4; j++)    dp[j]=nextdp[j];
        if(i%1000000==0)
        {
            cout<<i<<" ";
            printf("%d  %.4f\n",i, ret);
        }
    }
    return 0;
}

还是30.。。

于是想到有没有简单的方法。。。其实可以观察到当趋于无穷的时候，此系统的期望的概率转移是趋于稳定的！其实任何系统在无穷步之后，都是期望稳定的！！(废话,但很重要！)

所以，从0 到1 所需要的期望步数很简单就是1. 从1到2的期望步数假设是X ，则在走了一步之后，我们分情况讨论所处位置。可以列出  X = 1+ 1/3*X + 1/3*(1+X)  所以X=4 ,从1 都2 的期望步数是4. 同理，从2-3 X = 1+ 4/9*X + 4/9*(4+X)   X =25. 从2到3的期望步数是25. 所以从0到3的期望步数是 30.。。。。。。。

坑爹啊！！！！！！！！！！！！

使用第一种思路可以求，问题是那个矩阵A太坑爹。。。看看他的特征值。。。。eig(A)

ans =

   -1588/3201 

    1072/3461 

     457/474  

还要带着n次方去求解dp[2][k]的通项。。。杀了我吧。。第二种方法是解决这类问题的万金油啊。反正系统达到稳态，那就直接上稳态公式吧。其实求解差分方程组的解法中，隐含使用的条件就是稳态方程。。。殊归同途啊。。。



Sosi 2012-10-23 11:39 发表评论
]]>SRM 304 Uhttp://www.cppblog.com/sosi/archive/2012/06/01/177103.htmlSosiSosiFri, 01 Jun 2012 10:55:00 GMThttp://www.cppblog.com/sosi/archive/2012/06/01/177103.htmlhttp://www.cppblog.com/sosi/comments/177103.htmlhttp://www.cppblog.com/sosi/archive/2012/06/01/177103.html#Feedback0http://www.cppblog.com/sosi/comments/commentRss/177103.htmlhttp://www.cppblog.com/sosi/services/trackbacks/177103.htmlDIV2 1000

给定一个凸N变形,可以调整任意多个顶点,但是距离只能是1 ,不能调整两个相邻的顶点,求变化之后的多边形的最大增加的面积是多少?

 

这个问题是一个动态规划问题,为了使问题能够达到线性而不是圆形循环的,我们需要考虑3中情况. 一开始写了一个贪心的枚举,但能够找到反例.

 

double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2));
}
class PolyMove
{
    public:
        double addedArea(vector <int> x, vector <int> y)
        {
            // It is a dynamic programming problem
            int n = x.size();
            double ret = 0.0f;
            vector<double> best(n, 0.0);

            // first case
            best[0]=0.0f; best[1]=0.0f;
            for(int i=2; i<n; i++)
                best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f);
            ret = best[n-1];

            //second case
            for(int i=0; i<n; i++) best[i]=0.0f;
            best[0]=0.0f; best[1]= dis(x[n-1], y[n-1], x[1],y[1])*0.5f;
            best[2]=best[1];
            for(int i=3; i<n; i++)
                best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f);

           ret = max(best[n-1], ret);


            // third case<F5>
            for(int i=0; i<n; i++) best[i]=0.0f;
            best[0]=  dis(x[n-2], y[n-2], x[0], y[0])*0.5f;
            best[1]=best[0];
            for(int i=2; i<n-1; i++)
                best[i]= max(best[i-1], best[i-2]+  dis(x[i-2], y[i-2], x[i], y[i])*0.5f);
            ret = max(ret , best[n-2]);

            return ret;
        }

};


Sosi 2012-06-01 18:55 发表评论
]]>