社区讨论
SPJ有问题吧
P2763试题库问题参与者 6已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi5i5lor
- 此快照首次捕获于
- 2025/11/19 12:28 4 个月前
- 此快照最后确认于
- 2025/11/19 12:28 4 个月前
我的代码明明是错的,其实连样例都么过,但却a掉了,具体错误是输出方案时的序号本应每行1: 2:3:排,而我每行都写的1:结果奇迹ac
下面是错误代码
···cpp
CPP#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e4+10;
const int inf=1e9;
struct jgt{
int x,y,remain,next;
} bian[10*maxn];
int k,n,tot=-1,s,t,dis[maxn],head[maxn],ans,tar,text[25][10001];
int min(int a,int b){ if (a>b) return b; return a;}
void add_edge(int a,int b,int c)
{
tot++;
bian[tot].x=a;
bian[tot].y=b;
bian[tot].remain=c;
bian[tot].next=head[a];
head[a]=tot;
}
bool bfs()
{
int front=0,tail=0,h[10*maxn];
memset(dis,0x7f,sizeof(dis));
h[tail++]=s;
dis[s]=1;
while (front<tail)
{
front++;
int now=h[front];
for (int tmp=head[now];tmp!=-1;tmp=bian[tmp].next)
{
int v=bian[tmp].y;
if (dis[v]>=0x7f&&bian[tmp].remain>0)
h[++tail]=v,dis[v]=dis[now]+1;
}
}
if (dis[t]>=0x7f) return false;
return true;
}
int dfs(int k,int limit)
{
int flow=0;
if (k==t||limit==0) return limit;
for (int tmp=head[k];tmp!=-1;tmp=bian[tmp].next)
{
int v=bian[tmp].y;
if (dis[v]==dis[k]+1)
{
int d=dfs(v,min(limit,bian[tmp].remain));
if (d>0)
{
flow+=d;
limit-=d;
bian[tmp].remain-=d;
bian[tmp^1].remain+=d;
}
}
}
return flow;
}
int main()
{
int i,j,c,d;
scanf("%d%d",&k,&n);
s=0;
t=n+k+1;
memset(head,-1,sizeof(head));
for (i=1;i<=k;i++)//各种题型向汇点连边
scanf("%d",&c),add_edge(n+i,t,c),add_edge(t,n+i,0),tar+=c;
for (i=1;i<=n;i++)//原点向每个题连容量为1的边
add_edge(s,i,1),add_edge(i,s,0);
for (i=1;i<=n;i++)
{
scanf("%d",&d);
for (j=1;j<=d;j++)//该题与其所属类型连边
scanf("%d",&c),add_edge(i,c+n,1),add_edge(c+n,i,0);
}
while (bfs())
ans+=dfs(s,inf);
if (ans!=tar){
printf("No Solution!");
return 0;
}
for (i=0;i<=tot;i+=2)
if (bian[i].y>=1&&bian[i].y<=n&&bian[i].remain==0)
{
int u=bian[i].y;
for (int tmp=head[bian[i].y];tmp!=-1;tmp=bian[tmp].next)
{
int v=bian[tmp].y;
if (v>=n+1&&v<=n+k&&bian[tmp].remain==0)
text[v-n][0]++,text[v-n][text[v-n][0]]=bian[i].y;
}
}
for (i=1;i<=k;i++)
{
printf("1: ");//就是这个地方输出错误,而且错的十分明显!!!!!!!
for (j=1;j<=text[i][0];j++)
printf("%d ",text[i][j]);
printf("\n");
}
}
···
回复
共 5 条回复,欢迎继续交流。
正在加载回复...