自己怎么样做网站,wordpress语言选项,做app得多少钱,做网站不会框架架设电话线
jzoj 2132
题目大意#xff1a;
给你一个图#xff0c;让你从1走到n#xff0c;问如果可以使k条路的代价变为0#xff08;自选#xff09;#xff0c;那途中走的路的最大值最小是多少
样例输入
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6输入说明…架设电话线
jzoj 2132
题目大意
给你一个图让你从1走到n问如果可以使k条路的代价变为0自选那途中走的路的最大值最小是多少
样例输入
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信公司可以免费为FJ连结一对电话线杆。
样例输出
4输出说明:
FJ选择如下的连结方案1-33-22-5这3对电话线杆间需要的电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线于是他所需要购买的电话线的最大长度为4。
数据范围
1⩽K⩽N⩽1,0001 \leqslant K\leqslant N \leqslant 1,0001⩽K⩽N⩽1,000 1⩽P⩽10,0001 \leqslant P\leqslant 10,0001⩽P⩽10,000 1⩽Li⩽1,000,0001 \leqslant L_i \leqslant 1,000,0001⩽Li⩽1,000,000 n为点的总数p为路的总数l为路的权值K如题目大意所叙
解题思路
我们可以先二分答案然后把权值大于midmidmid的路设为1然后跑spfa如果结果小于k就说明可行
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,m,k,x,y,z,l,r,pd,mid,tot,top,head[1500],b[1500],p[1500],s[10500],pp[1000500];
struct rec
{int to,l,next;
}a[20500];
int js(int aa,int bb){return aabb?1:0;}//大于条件的就是1
int spfa(int maxx)
{memset(b,127/3,sizeof(b));//预处理memset(p,0,sizeof(p));queueintd;d.push(1);p[1]1;b[1]0;while(!d.empty())//spfa{int hd.front();d.pop();for (int ihead[h];i;ia[i].next)if (b[h]js(a[i].l,maxx)b[a[i].to]){b[a[i].to]b[h]js(a[i].l,maxx);if (!p[a[i].to]){p[a[i].to]1;d.push(a[i].to);}}p[h]0;}if (b[n]b[0]) return 0;//无解else if (b[n]k) return 1;//可行else return 2;//不可行
}
int main()
{scanf(%d %d %d,n,m,k);for (int i1;im;i){scanf(%d %d %d,x,y,z);a[tot].toy;//存边a[tot].lz;a[tot].nexthead[x];head[x]tot;a[tot].tox;a[tot].lz;a[tot].nexthead[y];head[y]tot;if (!pp[z]) s[top]z;//把所有的权值存进来用于二分}s[top]0;//为了处理k最小边数sort(s1,s1top);//排序l1;rtop;while(lr){mid(lr)1;//求中间值pdspfa(s[mid]);if (!pd) {printf(-1);return 0;}else if (pd1) rmid;else lmid1;}printf(%d,s[l]);
}
