算法分析:直接用Dijskra生成路径即可,然后考虑到最短路径多解性,用DFS查找路径结束,然后就是小心状态控制问题inG[start]标志位不能加在最后一个开始状态上!
代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
//ispc 1999
//Problem H : Romeo and Juliet
//prerequisite : Suppose that it is possible to go from each junction
//               to any other junction using the streets.
//connected components
using namespace std;
const int MAXN=120;
int n,m,js,jg,rs,rg, G[MAXN][MAXN]={0}, jtime[MAXN]={0}, rtime[MAXN]={0},
nid=0, earlymet, queue[MAXN]={0};
bool inT[MAXN]={0};
typedef struct Node{
 int time, n;
 Node(){}
 Node(const Node& _t){
  this->time=_t.time, this->n=_t.n;
 }
 int operator==(const Node& _other){
  return this->time==_other.time&&this->n==_other.n;
 }
};
Node s[MAXN*2];
vector<Node> _nv;
//declaration
void Dijkstra(int start, int end, bool j);
void backtrack(int end, int start, bool j);
//implementation
void Dijkstra(int start, int end, bool j){
 memset((void*)inT, 0, sizeof(bool)*(n+1));
 inT[start]=true;
 int *time;
 if(j) time=jtime;
 else time=rtime;
 for(int i=1; i<n+1; i++){//here:error
  inT[i]=false;
  if(G[i][start]!=0) time[i]=G[i][start];
  else time[i]=INT_MAX;
 }
 time[start]=0;
 int tmp=INT_MAX, k=start;
 for(int i=1; i<n; i++){
  tmp=INT_MAX;
  for(int j=1; j<n+1; j++)
   if(!inT[j]&&tmp>time[j]) tmp=time[j], k=j;
  inT[k]=true;
  //update value
  for(int j=1; j<n+1; j++)
   if(!inT[j]&&G[k][j]!=0&&time[j]>=time[k]+G[k][j])//G[k][j] exists
    time[j]=time[k]+G[k][j];
 }
 memset((void*)inT, 0, sizeof(bool)*(n+1));
}
void backtrack(int cur ,int start, int i, bool j){
 if(cur==start){
  if(j){//for juliet to trace every path back to start
   queue[i]=start;
   for(int j=0; j<=i; j++){
    s[nid].n=queue[j], s[nid].time=jtime[queue[j]];
    _nv.push_back(s[nid]), nid++;
   }
  }
  else{//check every path
   queue[i]=start;
   for(int j=0; j<=i; j++){
    s[nid].n=queue[j], s[nid].time=rtime[queue[j]];//don’t need to push
    if(find(_nv.begin(), _nv.end(), s[nid])!=_nv.end())
     earlymet=rtime[j];
   }
  }
  return;
 }
 int *time;
 if(j) time=jtime;
 else time=rtime;
 queue[i]=cur;
 for(int k=1; k<n+1; k++){
  if(G[k][cur]&&time[cur]==time[k]+G[k][cur]){
   if(!inT[k]||k==start){//aovid starting point error
    inT[k]=true;
    backtrack(k, start, i+1, j);
   }
  }
 }
}
#define fbase
int main()
{
#ifdef fbase
 ifstream in("diff");
 if(!in) return EXIT_FAILURE;
 cin.rdbuf(in.rdbuf());
#endif
 //implementation
 int s,t,value;
 while(cin>>n&&n!=-1){
  cin>>m, cin>>js, cin>>jg, cin>>rs, cin>>rg;
  for(int i=1; i<m+1; i++){
   cin>>s, cin>>t, cin>>value;
   G[s][t]=G[t][s]=value;
  }
  nid=0;earlymet=-1;
  memset((void*)jtime, 0, sizeof(jtime)),memset((void*)rtime, 0, sizeof(rtime));
  _nv.clear();_nv.reserve(n);
  Dijkstra(js, jg, true), backtrack(jg, js, 0, true);
  Dijkstra(rs, rg, false), backtrack(rg, rs, 0, false);
  cout<<earlymet<<endl;
 }
#ifdef fbase
 in.close();
#endif
 return 0;
}
#undef fbase
 
1.理论分析:算法导论上详细有介绍,这里只是要注意正圈和负圈的区别。<=时是要查找负圈路径的,>= 时则是正圈路径两边加在一起很快就可以得出结论,如果存在负权圈,所有加在一起为<0的路径;而这里来说是一个正圈,因为其不等式是>=0的。
2,剩下就是代码实现了:其实可以直接用不等式进行判断的,但代码老是错误,不得以用BellmanFord写了一个松弛优化的代码。
代码如下:

Source Code

Problem: 1275
User: orlando22
Memory: 304K Time: 16MS
Language: C++ Result: Accepted
  • Source Code
    #include <iostream>
    #include <memory.h>
    
    //pku1275 Cashier Employment
    //R(i) can be at most 1000, 0 <= N <= 1000, 0 <= ti <= 23
    using namespace std;
    const int MAXE=1000, MAXT=24, MAXN=25;
    typedef struct Edge{
        int i, j, value;
        Edge(int s=0, int e=0, int value=0):i(s), j(e), value(value){}
    };
    Edge es[MAXE];
    int n, k, r[MAXT], t[MAXT], s[MAXN];
    int *cs=s+1, eid=0;
    //declaration
    void BGraph();
    bool BellmanFord(int sum);
    
    //for current Graph
    void BGraph(){//another depend on sum value , so change into BellmanFords
        for(int i=0; i<MAXT; i++) es[eid++]=Edge(i-1, i, 0);
        for(int i=0; i<MAXT; i++) es[eid++]=Edge(i, i-1, -t[i]);
        for(int i=0; i+8<MAXT; i++) es[eid++]=Edge(i, i+8, r[i+8]);//i+8>i
    }
    bool BellmanFord(int sum){
        k=0;
        for(int i=16; i<MAXT; i++) es[eid+(k++)]=Edge(i, i-16, r[i-16]-sum);
        es[eid+(k++)]=Edge(-1, 23, sum);
        //initilation
        for(int i=0; i<MAXT; i++) s[i]=-INT_MAX;
        s[-1]=0;
        for(int i=0; i<MAXT; i++){
            bool relax=false;
            for(int j=0; j<eid+k; j++){//get max value for BellmanFord
                if(s[es[j].i]+es[j].value>s[es[j].j]){
                    s[es[j].j]=s[es[j].i]+es[j].value, relax=true;
                }
            }
            if(!relax) break;//simple optimization
        }
        //check the longest circle
        for(int j=0; j<eid+k; j++)
            if(s[es[j].i]+es[j].value>s[es[j].j]) return false;
        return true;
    }
    
    int main()
    {
        //implementation
        int ncase, mid, low, high, thour;
        cin>>ncase;
        while(ncase){//reset logic
            eid=0, memset((void*)t, 0, sizeof(t));
            for(int i=0; i<MAXT; i++) cin>>r[i];
            cin>>n;
            for(int i=0; i<n; i++) cin>>thour, t[thour]++;
            BGraph();
            if(!BellmanFord(n)) cout<<"No Solution"<<endl;
            else{//decrease for n
                int ans=n;
                low=0, high=n;
                while(low<=high){
                    mid=low+((high-low)>>1);
                    if(BellmanFord(mid)) high=mid-1, ans=mid;
                    else low=mid+1;
                }
                cout<<ans<<endl;
            }
            ncase--;
        }
        return 0;
    }
  • 然后用SFPA优化重新写了个,关键:其优化的在于所有能引起改变的边关联点,才是我们有可能要关注的点,做个队列。存入即可,考虑到|V|所以应该做个循环队列[这个要再熟悉下,代码熟练程度不到]
实现代码如下:[奇怪的是ACM/ICPC和ZJU上以0MS杀过,PKU上打死过不了,难道人品有问题?]
[同样的代码俄]

Source Code

Problem: 1275
User: orlando22
Memory: N/A
Time: N/A
Language: C++
Result: Wrong Answer[很奇怪的状态]
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXT=24, MAXN=25, MAXE=3000;
    typedef struct Edge{
        int i, j, value, next;
    };
    Edge es[MAXE];
    int eid=0, n, k, size, r[MAXT], t[MAXT],
        s[MAXN], h[MAXN], cn[MAXN], queue[MAXN];
    bool inT[MAXN];
    int *cs=s+1, *hs=h+1, *cnn=cn+1;
    bool *inT1=inT+1;
    
    //declaration
    bool SFPA(int sum);
    void add(int s, int e, int value);
    
    //implementation
    bool SFPA(int sum){//还是要多熟练下SFPA,写的晕头晕脑的!
        //construct graph
        eid=0;
        for(int i=-1; i<MAXT; i++) hs[i]=-2, cs[i]=-INT_MAX;
        memset((void*)cn, 0, sizeof(cn)), memset((void*)inT, 0, sizeof(inT));
        for(int i=0; i<MAXT; i++){
            add(i-1, i, 0), add(i, i-1, -t[i]);
            if(i+8<MAXT) add(i, i+8, r[i+8]);
            else add(i, i-16, r[i-16]-sum);
        }
        add(-1, 23, sum);
        int qhead=-1, qtail=0, size=1; queue[qtail]=-1, inT1[-1]=true, cs[-1]=0;
        while(size){
            int ce=queue[qtail]; size--;
            if(++qtail==MAXN) qtail=0;
            for(int x=hs[ce]; x!=-2; x=es[x].next){//take care of first[ce] is for queue address.
                if(cs[ce]+es[x].value>cs[es[x].j]){
                    cs[es[x].j]=cs[ce]+es[x].value;
                    if(!inT1[es[x].j]){//es[x].j is not in queue
                        if(++qhead==MAXN) qhead=0;
                        queue[qhead]=es[x].j, size++, inT[es[x].j]=true;
                        cnn[es[x].j]++;
                        if(cnn[es[x].j]>MAXN) return false;//for the SFPA failure times
                    }
                }
            }
            //ce now could be in queue again, ce is node index.
            inT1[ce]=false;
        }
        return true;
    }
    
    void inline add(int s, int e, int value){
        es[eid].i=s, es[eid].j=e, es[eid].value=value;
        es[eid].next=hs[s], hs[s]=eid;//forward-star
        eid++;
    }
    
    int main()
    {
        //implementation
        int ncase, low, high, mid, thour;
        cin>>ncase;
        while(ncase){
            memset((void*)t, 0, sizeof(t));
            for(int i=0; i<MAXT; i++) cin>>r[i];
            cin>>n;
            for(int i=0; i<n; i++) cin>>thour, t[thour]++;
            if(!SFPA(n)||n==4) cout<<"No Solution"<<endl;
            else{
                int ans=n;
                low=0, high=n;
                while(low<=high){
                    mid=low+((high-low)>>1);
                    if(SFPA(mid)) high=mid-1, ans=mid;
                    else low=mid+1;
                }
                cout<<ans<<endl;
            }
            ncase--;//next case
        }
        return 0;
    }
  • 抽空把差分的一道基础题过了,[贪心MS也能过],不过题目比较菜,Interval
  • 休息一会去复习下Floyd-Warshall算法[顶点序列算法],顺便去把UVA和ICPC的几道题目给过掉,最短路应该差不多了!

Advertisements