danihao123's Blog

这个可以有啊（赞赏）！

我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。

然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。

然后这样可以发现，用$1$到$n$的路径来异或一个环，可以得到新的一条$1$到$n$的路径。

这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条$1$到$n$的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……

代码：

/**************************************************************
    Problem: 2115
    User: danihao123
    Language: C++
    Result: Accepted
    Time:652 ms
    Memory:6544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = d;
  return cnt;
}
void ins_edge(int u, int v, ll d) {
  int e1 = add_edge(u, v, d);
  int e2 = add_edge(v, u, d);
  rev[e1] = e2; rev[e2] = e1;
}
 
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
  for(int i = 60; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
  vis[x] = true; sum[x] = s;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    int v = to[i];
    used[i] = used[rev[i]] = true;
    if(vis[v]) {
      insert((s ^ sum[v]) ^ dist[i]);
    } else {
      dfs(v, s ^ dist[i]);
    }
  }
}
 
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; ll d;
    scanf("%d%d", &u, &v); scanf(LO, &d);
    ins_edge(u, v, d);
  }
  dfs(1, 0LL);
  ll ret = sum[n];
  for(int i = 60; i >= 0; i --) {
    if(!T[i]) continue;
    if(!(ret & (1LL << i))) {
      ret ^= T[i];
    }
  }
  printf(LO, ret); puts("");
  return 0;
}

又是一道分层图最短路水题……

我估计会卡SPFA（或许可能不卡？），所以再次写了pb_ds优化Dijkstra。

代码：

/**************************************************************
    Problem: 2662
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:868 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=51,maxk=51,maxm=2005;
int cnt=0;
int first[maxn];
int to[maxm],next[maxm];
int dist[maxm];
inline void Add_Edge(int x,int y,int z){
    cnt++;
    next[cnt]=first[x];
    first[x]=cnt;
    to[cnt]=y;
    dist[cnt]=z;
}
 
int d[maxn][maxk];
bitset<maxn> vis[maxk];
struct Node{
    int x,k,d;
    bool operator <(const Node& itt) const{
        return d<itt.d;
    }
    bool operator >(const Node& itt) const{
        return d>itt.d;
    }
};
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
inline void relax(int x,int y,int p){
    d[x][y]=p;
    if(ite[x][y]!=0)
        Q.modify(ite[x][y],(Node){x,y,p});
    else
        ite[x][y]=Q.push((Node){x,y,p});
}
int dij(){
    register int i,u,v,ans=0x7f7f7f7f;
    memset(d,0x7f,sizeof(d));
    d[1][0]=0;
    ite[1][0]=Q.push((Node){1,0,0});
    while(!Q.empty()){
        u=Q.top().x;
        v=Q.top().k;
        Q.pop();
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[to[i]][v+1]>(d[u][v]+dist[i]/2)){
                    relax(to[i],v+1,d[u][v]+dist[i]/2);
                }
            }
            if(d[to[i]][v]>d[u][v]+dist[i]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    for(i=0;i<=k;i++)
        ans=min(ans,d[n][i]);
    return ans;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    k=readint();
    for(i=1;i<=m;i++){
        u=readint();
        v=readint();
        d=readint();
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    writeint(dij());
    putchar('\n');
    return 0;
}