「zoj3229」Shoot the Bullet

2014年6月3日5,8022

Gensokyo is a world which exists quietly beside ours, separated by a mystical border. It is a utopia where humans and other beings such as fairies, youkai(phantoms), and gods live peacefully together. Shameimaru Aya is a crow tengu with the ability to manipulate wind who has been in Gensokyo for over 1000 years. She runs the Bunbunmaru News – a newspaper chock-full of rumors, and owns the Bunkachou – her record of interesting observations for Bunbunmaru News articles and pictures of beautiful danmaku(barrange) or cute girls living in Gensokyo. She is the biggest connoisseur of rumors about the girls of Gensokyo among the tengu. Her intelligence gathering abilities are the best in Gensokyo!

During the coming n days, Aya is planning to take many photos of m cute girls living in Gensokyo to write Bunbunmaru News daily and record at least G_x photos of girlx in total in the Bunkachou. At the k-th day, there are C_k targets, T_k1, T_k2, …, T_{kC_k}. The number of photos of target T_ki that Aya takes should be in range [L_ki, R_ki], if less, Aya cannot write an interesting article, if more, the girl will become angry and use her last spell card to attack Aya. What’s more, Aya cannot take more than D_kphotos at the k-th day. Under these constraints, the more photos, the better.

Aya is not good at solving this complex problem. So she comes to you, an earthling, for help.

Input

There are about 40 cases. Process to the end of file.

Each case begins with two integers 1 <= n <= 365, 1 <= m <= 1000. Then m integers, G₁, G₂, …, G_m in range [0, 10000]. Then n days. Each day begins with two integer 1 <= C <= 100, 0 <= D <= 30000. Then C different targets. Each target is described by three integers, 0 <= T < m, 0 <= L <= R <= 100.

Output

For each case, first output the number of photos Aya can take, -1 if it’s impossible to satisfy her needing. If there is a best strategy, output the number of photos of each girl Aya should take at each day on separate lines. The output must be in the same order as the input. If there are more than one best strategy, any one will be OK.

Output a blank line after each case.

Sample Input

2 3

12 12 12

3 18

0 3 9

1 3 9

2 3 9

3 18

0 3 9

1 3 9

2 3 9

2 3

12 12 12

3 18

0 3 9

1 3 9

2 3 9

3 18

0 0 3

1 3 6

2 6 9

2 3

12 12 12

3 15

0 3 9

1 3 9

2 3 9

3 21

0 0 3

1 3 6

2 6 12

Sample Output

-1

题解

首先S向每天连[0,day]的边，每一天与拍照的妹子连[l,r]的边，每个女孩和汇连[g,oo]的边

对于有源和汇的上下界网络流，只要T到S连一条[0,inf]的边，那么原图成为一个无源点汇点的循环流图，那么新建SS和TT，向每个点连边（即每一点的入流为正则源向其连，否则向汇连），求SS到TT的最大流判断满流

判断有解之后求最大流再做一次S到T的最大流

同时要去掉原来T到S的[0,inf]的边

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1000000000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,ans;
int head[1505],cur[1505],h[1505],q[1505],in[1505];
int day[505],low[100005];
struct data{int to,next,v;}e[100005];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs(int S,int T)
{
     memset(h,-1,sizeof(h));
     int t=0,w=1;q[0]=S;h[S]=0;
     while(t!=w)
     {
          int now=q[t];t++;
          for(int i=head[now];i;i=e[i].next)
              if(e[i].v&&h[e[i].to]==-1)
              {
                   h[e[i].to]=h[now]+1;
                   q[w++]=e[i].to;
              }
     }
     if(h[T]==-1)return 0;
     return 1;
}
int dfs(int x,int f,int T)
{
     if(x==T)return f;
     int w,used=0;
     for(int i=cur[x];i;i=e[i].next)
          if(h[e[i].to]==h[x]+1)
          {
               w=f-used;w=dfs(e[i].to,min(e[i].v,w),T);
               e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w;
               used+=w;if(used==f)return f;
          }
     if(!used)h[x]=1;
     return used;
}
void dinic(int S,int T)
{while(bfs(S,T)){for(int i=0;i<=n+m+3;i++)cur[i]=head[i];dfs(S,inf,T);}}
bool jud()
{
     int SS=n+m+2,TT=n+m+3;
     for(int i=0;i<=n+m+1;i++)
     {
          if(in[i]>0)insert(SS,i,in[i]);
          if(in[i]<0)insert(i,TT,-in[i]);
     }
     dinic(SS,TT);
     for(int i=head[SS];i;i=e[i].next)
         if(e[i].v)return 0;
     return 1;
}
int main()
{
     while(scanf("%d%d",&n,&m)!=EOF)
     {
          cnt=1;int S=0,T=n+m+1;
          ans=0;
          memset(head,0,sizeof(head));
          memset(in,0,sizeof(in));
          for(int i=1;i<=m;i++)
          {
               int g=read();
               in[T]+=g;
               in[i+n]-=g;
          }
          int ed=0;
          for(int i=1;i<=n;i++)
          {
               int x=read();day[i]=read();
               for(int j=1;j<=x;j++)
               {
                   int num=read();
                   low[++ed]=read();int r=read();
                   insert(i,n+num+1,r-low[ed]);
                   in[i]-=low[ed];
                   in[n+num+1]+=low[ed];
               }
          }
          for(int i=1;i<=n;i++)insert(S,i,day[i]);
          for(int i=1;i<=m;i++)insert(i+n,T,inf);
          insert(T,S,inf);
          if(jud())
          {
               dinic(S,T);insert(T,S,-inf);
               for(int i=head[S];i;i=e[i].next)
                   ans+=e[i^1].v;
               printf("%d\n",ans);
               for(int i=1;i<=ed;i++)
                   printf("%d\n",e[(i<<1)^1].v+low[i]);
          }
          else printf("-1\n");
          puts("");
     }
     return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,ans;

int head[1505],cur[1505],h[1505],q[1505],in[1505];

int day[505],low[100005];

struct data{int to,next,v;}e[100005];

void ins(int u,int v,int w)

{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,0);}

bool bfs(int S,int T)

{

memset(h,-1,sizeof(h));

int t=0,w=1;q[0]=S;h[S]=0;

while(t!=w)

{

int now=q[t];t++;

for(int i=head[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[w++]=e[i].to;

}

if(h[T]==-1)return 0;

return 1;

}

int dfs(int x,int f,int T)

{

if(x==T)return f;

int w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=f-used;w=dfs(e[i].to,min(e[i].v,w),T);

e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w;

used+=w;if(used==f)return f;

}

if(!used)h[x]=1;

return used;

}

void dinic(int S,int T)

{while(bfs(S,T)){for(int i=0;i<=n+m+3;i++)cur[i]=head[i];dfs(S,inf,T);}}

bool jud()

{

int SS=n+m+2,TT=n+m+3;

for(int i=0;i<=n+m+1;i++)

{

if(in[i]>0)insert(SS,i,in[i]);

if(in[i]<0)insert(i,TT,-in[i]);

}

dinic(SS,TT);

for(int i=head[SS];i;i=e[i].next)

if(e[i].v)return 0;

return 1;

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

cnt=1;int S=0,T=n+m+1;

ans=0;

memset(head,0,sizeof(head));

memset(in,0,sizeof(in));

for(int i=1;i<=m;i++)

{

int g=read();

in[T]+=g;

in[i+n]-=g;

}

int ed=0;

for(int i=1;i<=n;i++)

{

int x=read();day[i]=read();

for(int j=1;j<=x;j++)

{

int num=read();

low[++ed]=read();int r=read();

insert(i,n+num+1,r-low[ed]);

in[i]-=low[ed];

in[n+num+1]+=low[ed];

}

for(int i=1;i<=n;i++)insert(S,i,day[i]);

for(int i=1;i<=m;i++)insert(i+n,T,inf);

insert(T,S,inf);

if(jud())

{

dinic(S,T);insert(T,S,-inf);

for(int i=head[S];i;i=e[i].next)

ans+=e[i^1].v;

printf("%d\n",ans);

for(int i=1;i<=ed;i++)

printf("%d\n",e[(i<<1)^1].v+low[i]);

}

else printf("-1\n");

puts("");

}

return 0;

}

« 「zoj2314」Reactor Cooling 「POJ2396」Budget »

233

这题zoj上好像挂了，一直Judge Internal Error

12315

……..

hzwer.com _ Home | http://hzwer.com

「zoj3229」Shoot the Bullet

分类目录

热门文章

Myfriends

近期评论