首页 > 代码库 > 【HAOI2015】PG图

【HAOI2015】PG图

2024-09-19 23:37:09   214人阅读

Description

背景
LDN不知道为什么特别喜欢PG，也许是某种原因吧……
有一天，他发明了一个游戏“PG图”。
问题描述

给定一个有向图，每条边都有一个权值。
每次你可以选择一个节点u和一个整数d，把所有以u为终点的边的权值减小d，把所有以u为起点的边的权值加上d。最后要让所有边的权值的最小值为正且尽量大。

Input

输入包含若干组数据。
每组数据第一行为两个整数n和m(n<=500,m<=2700)，表示点和边的个数。
以下m行，每行包括3个整数u,v,w，表示u -> v有一条边权为w的边。(1<= u,v<= n, -10000<= w<= 10000)

Output

对于每组数据，输出边权最小值的最大值；
如果无法让所有边权都大于0，输出“No Solution”；
如果边权最小值可以无限大，输出“Infinite”。

Sample Input

2 1
1 2 10
2 1
1 2 -10
3 3
1 2 4
2 3 2
3 1 5
4 5
2 3 4
4 2 5
3 4 2
3 1 0
1 2 -1

Sample Output

Infinite
Infinite
3
1

Hint

数据范围与约定

对于30%的数据:2<= n<= 10,1<= m<= 100
对于60%的数据:2<= n<= 100,1<= m<=1000
对于100%的数据:2<= n<= 500,1<= m<=2700

Source

图论 ， 差分约束

 

<style>p { margin-bottom: 0.25cm; line-height: 120% }</style>

思路{

　　这种看起来无从下手的东东就往查分约束上想想。。。。

　　设sum[x]为改变x的出度的∑d。

　　设答案为mid，有dis(i,j)+sum[a]-sum[b]>=mid;

　　变形 sum[b]-sum[a]<=dis(i,j)-mid;

　　插分约束加二分答案。枚举每一个点，求最短路因为要全部满足要求

　　但是，叶闻捷大神的dfs找环真是妙不可言啊！！！！！！

　　比我的傻逼SPFA快了10多倍！！！！

　　(OrzOrzOrzOrz)

}

 

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<ctime>
 8 #include<cmath>
 9 #include<list>
10 #include<deque>
11 #include<stack>
12 #include<map>
13 #include<set>
14 #define RG register
15 #define LL long long
16 #define dd double
17 #define maxx 501
18 #define mid ((l+r)>>1)
19 #define make(x) vis[x]=true;
20 #define made(x) vis[x]=false;
21 using namespace std;
22 struct ed{
23 int nxt,to,c;
24 }e[2770];bool vis[maxx];
25 int head[maxx],tot,n,m,dis[maxx],cnt[maxx];
26 void add(int u,int v,int c){e[tot].nxt=head[u];e[tot].c=c;e[tot].to=v;head[u]=tot++;}
27 bool SPFA(int s,int num){
28   make(s)
29     for(int i=head[s];i!=-1;i=e[i].nxt)if(dis[e[i].to]>dis[s]+e[i].c-num){
30         if(vis[e[i].to])return 1;
31         dis[e[i].to]=dis[s]+e[i].c-num;
32         if(SPFA(e[i].to,num))return 1;
33       }return made(s);
34 }
35 int main(){
36   while(scanf("%d%d",&n,&m)!=EOF){
37     memset(head,-1,sizeof(head));tot=0;
38     for(int i=1;i<=m;++i){
39       int u,v,w;
40       scanf("%d%d%d",&u,&v,&w);
41       add(u,v,w);
42     }
43     int l=1,r=100000;
44     while(l<=r){
45       bool flag=true;
46       for(int i=1;i<=n;++i){
47         memset(vis,false,sizeof(vis));
48         memset(dis,127,sizeof(dis));
49         if(SPFA(i,mid)){flag=false;break;}
50       }
51       if(!flag)r=mid-1;else l=mid+1;
52     }if(r>10000)cout<<"Infinite\n";
53     else if(!r)cout<<"No Solution\n";
54     else cout<<r<<‘\n‘;
55   }
56   return 0;
57 }

 

 

 

【HAOI2015】PG图


联系
我们