HDU 4738 쌍 연통 모 판 문제
3709 단어 HDU
제목: n 개의 점 을 정 하고 m 개의 방향 이 없 음
아래 m 줄 은 u, v, 변 가중치 를 나타 낸다.
모든 다리 에서 가장 작은 다리 의 값 을 구하 십시오. 출력 이 존재 하지 않 는 다 면 - 1
그림 이 처음부터 연결 되 지 않 거나 최소 값 이 0 이면 출력 1
쌍 연통 구교 나체 문제
큰 라운드 테스트 데 이 터 를 첨부 합 니 다:
#include <string.h>
#include <cstdio>
#include <vector>
#define N 1010
#define inf 10000000
using namespace std;
inline int Min(int a,int b){return a>b?b:a;}
vector<int>G[N];
int dis[N][N],bian[N][N];
int n,m,f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void Union(int u,int v){
int fa=find(u),fb=find(v);
f[fa]=fb;
}
struct node{
int u,v,d;
}edge[N];// n
int edgenum;
void PUT(int u,int v,int d){
node E={u,v,d};
edge[edgenum++]=E;
}
int pre[N],low[N],dfs_clock;
bool su;
int dfs(int u,int fa){// ,dfs(u, ) u ( ) pre
if(su)return 0;
int lowu=pre[u]= ++ dfs_clock;
int child=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!pre[v])
{
child++;
int lowv=dfs(v,u);
lowu = Min(lowu, lowv);
if(lowv > pre[u]&&bian[u][v]==1){PUT(u,v,dis[u][v]);if(dis[u][v]<=1)return 0;}
}
else if(pre[v] < pre[u] && v!=fa)
lowu = Min(lowu, pre[v]);
}
return low[u]=lowu;
}
void findcut(){
memset(pre,0,sizeof(pre));
dfs_clock=0;
dfs(1,-1);//dfs( , -1)
}
int main(){
int i,u,v,d;
while(scanf("%d %d",&n,&m),n)
{
memset(bian,0,sizeof(bian));
for(i=1;i<=n;i++)
{
G[i].clear();
f[i]=i;
for(int j=1;j<=n;j++)
dis[i][j]=inf;
}
while(m--)
{
scanf("%d %d %d",&u,&v,&d);
if(dis[u][v]==inf)
{
G[u].push_back(v); G[v].push_back(u);
Union(u,v);
}
dis[u][v]=dis[v][u]=Min(dis[u][v],d);
bian[u][v]++; bian[v][u]++;
}
bool fa=false; find(1);
for(i=1;i<=n;i++)if(find(i)!=f[1]){fa=true;break;}
if(fa){printf("0
");continue;}
su=false;
edgenum=0;
findcut();
if(edgenum)
{
int ans=inf;
for(i=0;i<edgenum;i++)ans=Min(ans,edge[i].d);
if(ans==inf)ans=-1;
else if(ans==0)ans=1;
printf("%d
",ans);
}
else printf("-1
");
}
return 0;
}
/*
3 3
1 2 7
2 3 4
3 1 4
3 2
1 2 7
2 3 4
3 4
1 2 7
2 1 7
2 3 4
3 2 4
4 3
1 2 1
1 2 3
3 4 4
4 4
1 2 1
1 2 3
3 4 4
2 4 6
4 5
1 2 1
1 2 3
3 4 4
2 4 6
1 3 0
4 5
4 3 0
3 4 4
2 4 6
2 3 0
1 3 0
2 1
1 2 0
4 2
1 2 3
1 3 5
4 5
1 2 3
2 3 4
1 3 5
4 3 7
4 3 6
4 4
1 2 3
2 3 4
1 3 5
4 3 6
4 4
1 2 4
1 3 5
4 3 6
3 4 7
6 7
1 2 1
1 3 2
2 3 3
3 4 4
4 6 5
4 5 6
5 6 7
5 6
1 2 3
1 3 4
2 3 5
3 4 7
3 5 8
5 4 9
8 9
1 8 1
5 1 2
1 7 3
1 4 4
1 2 5
4 3 6
3 2 7
5 6 8
6 7 9
6 6
1 4 1
1 2 4
2 5 4
5 6 4
3 6 4
4 3 2
6 5
1 2 4
2 5 4
5 6 4
3 6 4
4 3 2
8 10
1 8 1
5 1 2
1 7 3
1 4 4
1 2 5
4 3 6
3 2 7
5 6 8
6 7 9
8 1 2
3 3
1 2 7
1 3 1
1 3 4
0 0
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.