Tricks Device
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 389 Accepted Submission(s): 100
Problem Description Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇門遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb Zhang.
Input There are multiple test cases. Please process till EOF.
For each case,the first line must includes two integers, N(<=2000), M(<=60000). N is the total number of the chambers, M is the total number of the channels.
In the following M lines, every line must includes three numbers, and use ai、bi、li as channel i connecting chamber ai and bi(1<=ai,bi<=n), it costs li(0<li<=100) minute to pass channel i.
The entrance of the tomb is at the chamber one, the end of tomb is at the chamber N.
Output Output two numbers to stand for the answers of Dumb Zhang and Innocent Wu’s questions.
Sample Input
8 9
1 2 2
2 3 2
2 4 1
3 5 3
4 5 4
5 8 1
1 6 2
6 7 5
7 8 1
Sample Output
2 6
Source 2015 Multi-University Training Contest 1
Recommend We have carefully selected several similar problems for you: 5299 5298 5297 5296 5295 題意：給一個無向圖N個點M條邊,每條邊都有一個時間花費，Innocent Wu隻有用最短的時間去追 Dumb Zhang才能追上，但 Dumb Zhang不想讓他追上，他可以斷開任意邊，問至少要斷幾條邊，得答案1，答案2＝最多能讓他斷多少路使得WU仍能追上zhang。 解題：用SPFA求出從N到所有點的最短路，和到所有點最短路上最少經過的邊數numk[]，這樣可以得到答案2＝M－numk[1]。接下來就用最大流來做，關鍵在找增廣流時要添加一個滿足到達N點時是最短路。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define captype int
const int MAXN = 2010; //點的總數
const int MAXM = 400010; //邊的總數
const int INF = 1<<30;
struct EDG{
int to,next;
captype cap,flow;
int d;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN]; //每種距離(或可認為是高度)點的個數
int dis[MAXN]; //每個點到終點eNode 的最短距離
int cur[MAXN]; //cur[u] 表示從u點出發可流經 cur[u] 号邊
int pre[MAXN];
int D[MAXN], vist[MAXN], mindis;
void init(){
eid=0;
memset(head,-1,sizeof(head));
}
//有向邊 三個參數，無向邊4個參數
void addEdg(int u,int v,int d,captype rc=0){
edg[eid].to=v; edg[eid].next=head[u]; edg[eid].d=d;
edg[eid].cap=1; edg[eid].flow=0; head[u]=eid++;
edg[eid].to=u; edg[eid].next=head[v]; edg[eid].d=INF;
edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源點和彙點的總點個數，這個一定要注意
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
memcpy(cur,head,sizeof(head));
memset(vist,-1,sizeof(vist));
pre[sNode] = -1;
gap[0]=n;
captype ans=0; //最大流
vist[sNode]=0;
int u=sNode ,i ;
while(dis[sNode]<n){ //判斷從sNode點有沒有流向下一個相鄰的點
if(u==eNode){ //找到一條可增流的路
captype Min=INF ;
int inser;
for( i=pre[u]; i!=-1; i=pre[edg[i^1].to]) //從這條可增流的路找到最多可增的流量Min
if(Min>edg[i].cap-edg[i].flow){
Min=edg[i].cap-edg[i].flow;
inser=i;
}
for( i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
edg[i].flow+=Min;
edg[i^1].flow-=Min; //可回流的邊的流量
}
ans+=Min;
u=edg[inser^1].to;
continue;
}
bool flag = false; //判斷能否從u點出發可往相鄰點流
int v;
for( i=cur[u]; i!=-1; i=edg[i].next){
v=edg[i].to;
if(edg[i].cap>0&&vist[u]+edg[i].d+D[v]!=mindis)//如果是正流，則必須保證是最短的一條路，如果是逆流，表明v點己是在最短路上
continue;
vist[v]=mindis-D[v];
if( edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if(flag){
u=v;
continue;
}
//如果上面沒有找到一個可流的相鄰點，則改變出發點u的距離（也可認為是高度）為相鄰可流點的最小距離+1
int Mind= n;
for( i=head[u]; i!=-1; i=edg[i].next){
v=edg[i].to;
if(edg[i].cap>0&&vist[u]+edg[i].d+D[v]!=mindis)
continue;
vist[v]=mindis-D[v];
if( edg[i].cap-edg[i].flow>0 && Mind>dis[v]){
Mind=dis[v];
cur[u]=i;
}
}
gap[dis[u]]--;
if(gap[dis[u]]==0) return ans; //當dis[u]這種距離的點沒有了，也就不可能從源點出發找到一條增廣流路徑
//因為彙點到目前點的距離隻有一種，那麼從源點到彙點必然經過目前點，然而目前點又沒能找到可流向的點，那麼必然斷流
dis[u]=Mind+1;//如果找到一個可流的相鄰點，則距離為相鄰點距離+1，如果找不到，則為n+1
gap[dis[u]]++;
if(u!=sNode) u=edg[pre[u]^1].to; //退一條邊
}
return ans;
}
int numk[MAXN];
void spfa(int s,int t,int n){
queue<int>q;
int inq[MAXN]={0},i;
for( i=1; i<=n; i++)
D[i]=INF;
D[t]=0; numk[t]=0;
q.push(t);
while(!q.empty()){
int u=q.front(); q.pop();
inq[u]=0;
for( i=head[u]; i!=-1; i=edg[i].next)
if(edg[i].d==INF&&D[edg[i].to]>D[u]+edg[i^1].d){
D[edg[i].to]=D[u]+edg[i^1].d;
numk[edg[i].to]=numk[u]+1;
if(inq[edg[i].to]==0)
inq[edg[i].to]=1,q.push(edg[i].to);
}
else if(edg[i].d==INF&&D[edg[i].to]==D[u]+edg[i^1].d&&numk[edg[i].to]>numk[u]+1)
{
numk[edg[i].to]=numk[u]+1;
if(inq[edg[i].to]==0)
inq[edg[i].to]=1,q.push(edg[i].to);
}
}
}
int main()
{
int n,m,u,v,cost;
while(scanf("%d%d",&n,&m)>0)
{
init();
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&u,&v,&cost);
addEdg(u,v,cost);
addEdg(v,u,cost);
}
spfa(1,n,n);
int ans1,ans2;
ans2=m-numk[1];
mindis=D[1];
ans1=maxFlow_sap(1,n,n);
printf("%d %d\n",ans1,ans2);
}
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)