[BZOJ 1877][SDOI2009]晨跑

1877: [SDOI2009]晨跑
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 2688 Solved: 1441
[Submit][Status][Discuss]
Description

Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他

坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一

个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室

编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以

在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia耐力不太好，

他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。除了练空手道，Elaxia其他时间

都花在了学习和找MM上面，所有他想请你帮忙为他设计一套满足他要求的晨跑计划。

Input

第一行：两个数N,M。表示十字路口数和街道数。

接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。

N ≤ 200，M ≤ 20000。

Output

两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。

Sample Input

7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1

Sample Output

2 11

HINT

Source

Day1

题解

求好几条路径然后每条路径不能在十字路口(结点)处相交...典型的结点容量型最大流OwO

拆点然后建图就吼了2333

然而有一个坑点: 虽然题目只是说不能在十字路口处相交, 但是每条边实际上也只能经过一次...一开始把边权设成 $infty$ 然后直接 WA 掉...无意间改成 $1$ 之后就 $A$ 了...

(令人智熄的操作.png)

参考代码

GitHub

  1 #include <bits/stdc++.h>
  2 
  3 const int MAXV=1e3+10;
  4 const int MAXE=4e5+10;
  5 const int INFI=0x3F3F3F3F;
  6 
  7 struct Edge{
  8     int from;
  9     int to;
 10     int dis;
 11     int flow;
 12     Edge* rev;
 13     Edge* next;
 14 };
 15 Edge E[MAXE];
 16 Edge* head[MAXV];
 17 Edge* top=E;
 18 
 19 int v;
 20 int e;
 21 int clk;
 22 int dis[MAXV];
 23 int vis[MAXV];
 24 bool inq[MAXV];
 25 
 26 bool SPFA(int,int);
 27 int DFS(int,int,int);
 28 void Insert(int,int,int,int);
 29 std::pair<int,int> Dinic(int,int);
 30 
 31 int main(){
 32     int from,to,dis;
 33     scanf("%d%d",&v,&e);
 34     for(int i=0;i<e;i++){
 35         scanf("%d%d%d",&from,&to,&dis);
 36         Insert(from*2,to*2-1,dis,1);
 37     }
 38     for(int i=1;i<=v;i++){
 39         Insert(i*2-1,i*2,0,(i==1||i==v)?INFI:1);
 40     }
 41     std::pair<int,int> ans=Dinic(1,v*2);
 42     printf("%d %d
",ans.first,ans.second);
 43     return 0;
 44 }
 45 
 46 std::pair<int,int> Dinic(int s,int t){
 47     int cost=0,flow=0,tmp;
 48     while(++clk,SPFA(s,t)){
 49         tmp=DFS(s,INFI,t);
 50         cost+=tmp*dis[t];
 51         flow+=tmp;
 52     }
 53     return std::make_pair(flow,cost);
 54 }
 55 
 56 bool SPFA(int s,int t){
 57     memset(dis,0x3F,sizeof(dis));
 58     memset(inq,0,sizeof(inq));
 59     std::queue<int> q;
 60     q.push(s);
 61     dis[s]=0;
 62     inq[s]=true;
 63     while(!q.empty()){
 64         s=q.front();
 65         q.pop();
 66         inq[s]=false;
 67         for(Edge* i=head[s];i!=NULL;i=i->next){
 68             if(i->flow>0&&dis[s]+i->dis<dis[i->to]){
 69                 dis[i->to]=dis[s]+i->dis;
 70                 if(!inq[i->to]){
 71                     q.push(i->to);
 72                     vis[i->to]=true;
 73                 }
 74             }
 75         }
 76     }
 77     return dis[t]<INFI;
 78 }
 79 
 80 int DFS(int s,int flow,int t){
 81     if(s==t||flow<=0)
 82         return flow;
 83     int tmp=flow;
 84     int k;
 85     vis[s]=clk;
 86     for(Edge* i=head[s];i!=NULL&&tmp!=0;i=i->next){
 87         if(i->flow>0&&dis[i->to]==dis[s]+i->dis&&vis[i->to]!=clk){
 88             k=DFS(i->to,std::min(tmp,i->flow),t);
 89             tmp-=k;
 90             i->flow-=k;
 91             i->rev->flow+=k;
 92         }
 93     }
 94     return flow-tmp;
 95 }
 96 
 97 inline void Insert(int from,int to,int dis,int flow){
 98     top->from=from;
 99     top->to=to;
100     top->dis=dis;
101     top->flow=flow;
102     top->rev=top+1;
103     top->next=head[from];
104     head[from]=top++;
105 
106     top->from=to;
107     top->to=from;
108     top->dis=-dis;
109     top->flow=0;
110     top->rev=top-1;
111     top->next=head[to];
112     head[to]=top++;
113 }

Backup

日常图包