社区讨论

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 条回复,欢迎继续交流。

正在加载回复...