啊哈磊_编程从这里起步
标题:
求助lyt大佬快显灵!!!!!!!!!!!!!!!!!!
[打印本页]
作者:
睿利之刃
时间:
2019-1-29 17:24
标题:
求助lyt大佬快显灵!!!!!!!!!!!!!!!!!!
求作业四题题解,做出来之后就往里面发!!!!!
作者:
lyt0707
时间:
2019-1-29 17:25
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n,cnt,low[20009],flag[20009],num[20009],root,m,ans,gedian,book[20009],t,hahaha=0,ansx=0;
long long u;
vector <int> e[20009];
void dfs(int cur,int father)
{
int child=0,i;
cnt++;
num[cur]=cnt;
low[cur]=cnt;
for(i=0;i<e[cur].size();i++)
{
int v = e[cur][i];
if(num[v]==0)
{
child++;
dfs(v,cur);
low[cur] = min(low[cur],low[v]);
if(cur!=root && low[v]>=num[cur])
{
flag[cur]=1;
}
if(cur==root && child>=2)
{
flag[cur]=1;
}
}
else
{
if(v!=father)
{
low[cur]=min(low[cur],num[v]);
}
}
}
return;
}
void use(int v)
{
if(book[v]==t)
{
return;
}
book[v]=t;
if(flag[v]==1)
{
gedian++;
return;
}
ans++;
for(int x=0;x<e[v].size();x++)
{
use(e[v][x]);
}
return;
}
int main()
{
int i,j;
while(scanf("%d",&m) && m!=0)
{
cnt=0;
memset(flag,0,sizeof(flag));
memset(book,0,sizeof(book));
memset(low,0,sizeof(low));
memset(num,0,sizeof(num));
gedian=0;
ans=0;
t=-1;
n=0;
u=1;
for(i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
n=max(a,n);
n=max(b,n);
e[a].push_back(b);
e[b].push_back(a);
}
for(i=1;i<=n;i++)
{
if(num[i]==0)
{
root=i;
dfs(root,root);
}
}
u=1;
for(i=1;i<=n;i++)
{
if(book[i]==0 && flag[i]!=1)
{
use(i);
t--;
if(gedian==1)
{
ansx++;
u=u*ans;
}
ans=0;
gedian=0;
}
}
hahaha++;
int h;
h=n*(n-1)/2;
if(ansx==0)
{
printf("Case %d: 2 %d\n",hahaha,h);
}
else
{
printf("Case %d: %d %lld\n",hahaha,ansx,u);
}
ansx=0;
for(i=1;i<=n;i++)
{
e[i].clear();
}
}
return 0;
}
复制代码
作者:
lyt0707
时间:
2019-1-29 17:29
游览农场
#include<cstdio>
using namespace std;
struct node
{
int s;
int e;
int f;
int c;
};
struct node edge[30000];
int n,m,sum,inf=999999999;
int book[30000],dis[1001],father[1001];
int bellman()
{
int i,k;
for(i=0;i<=n+1;i++)
{
father[i]=-1;
dis[i]=inf;
}
dis[0]=0;
for(k=0;k<=n+1;k++)
for(i=1;i<=m;i++)
{
if(edge[i].c==0) continue;
if(dis[edge[i].e]>dis[edge[i].s]+edge[i].f)
{
dis[edge[i].e]=dis[edge[i].s]+edge[i].f;
father[edge[i].e]=i;
}
}
if(dis[n+1]==inf) return 0;
return 1;
}
void dfs()
{
int u,x,i;
while(bellman())
{
u=n+1;
while(father[u]!=-1)
{
x=father[u];
if(x<=m-4)
{
edge[x].c=0;
edge[book[x]].f=-1;
}
else
{
edge[x].c-=1;
edge[book[x]].c+=1;
}
u=edge[x].s;
}
sum+=dis[n+1];
}
return ;
}
int main()
{
int i,t1,t2,t3;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
edge[i].s=t1;
edge[i].e=t2;
edge[i].f=t3;
edge[i].c=1;
book[i]=i+m;
edge[i+m].s=t2;
edge[i+m].e=t1;
edge[i+m].f=t3;
edge[i+m].c=1;
book[i+m]=i;
}
m=m*2;
edge[m+1].s=0;
edge[m+1].e=1;
edge[m+1].f=0;
edge[m+1].c=2;
book[m+1]=m+2;
edge[m+2].s=1;
edge[m+2].e=0;
edge[m+2].f=0;
edge[m+2].c=0;
book[m+2]=m+1;
edge[m+3].s=n;
edge[m+3].e=n+1;
edge[m+3].f=0;
edge[m+3].c=2;
book[m+3]=m+4;
edge[m+4].s=n+1;
edge[m+4].e=n;
edge[m+4].f=0;
edge[m+4].c=0;
book[m+4]=m+3;
m=m+4;
dfs();
printf("%d",sum);
return 0;
}
复制代码
作者:
Forinser
时间:
2019-1-30 12:01
lyt0707 发表于 2019-1-29 17:29
游览农场
bellman+DFS吗?做出来倒是挺妙的
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2