\u8fd9\u4e00\u9898\u662fSCOI2007\u4fee\u8f66\u7684\u5a01\u529b\u52a0\u5f3a\u7248\u3002
\n\u7528\u5e38\u89c4\u7684\u5199\u6cd5\u663e\u7136\u662f\u65e0\u6cd5\u901a\u8fc7\u7684\u3002
\n\u6211\u4eec\u8003\u8651\u52a8\u6001\u52a0\u8fb9\u3002
\n\u8fd9\u6837\u5c31\u53ef\u4ee5\u6700\u5c0f\u5316\u6bcf\u4e00\u6b21\u677e\u5f1b\u5e26\u6765\u7684\u5f71\u54cd\uff0c\u4e8e\u662f\u590d\u6742\u5ea6\u5c31\u53d8\u6210\u4e86O(\u80fd\u8fc7)
\n\uff08\u624d\u602a\u5462\u3002\u6211\u5361\u5e38\u5361\u4e86\u534a\u5929\u7ed3\u679c\u8fd8\u662f\u5f00\u4e86O2\u624d\u8fc7\u3002\uff09
\n\uff08\u8d76\u7d27\u5b66zkw\u8d39\u7528\u6d41\uff09 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<queue>\n#define calc(I,J) ((J-1)*sm+I)\n#define calc2(I) (I+sm*m)\n\nnamespace IO{\n\tconst int S = 1E6;\n\tchar buf[S];\n\tint len=0,pos=0;\n\tinline char frc(){\n\t\tif(len==pos){pos=0,len=fread(buf,1,S,stdin);}\n\t\tif(len==pos){exit(0);}else{putchar(buf[pos]);return buf[pos++];};\n\t}\n\tinline int fri(){\n\t\tint fr=1,ch=frc(),x=0;\n\t\twhile(ch<=32)ch=frc();\n\t\tif(ch=='-')fr=-1,ch=frc();\n\t\twhile('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=frc();\n\t\tputchar(ch);\n\t\treturn x*fr;\n\t}\n}\n\nconst int INF = 0x3f3f3f3f;\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint c;\n\tint nxt;\n}e[6600005];\nint h[90005],et=-1;\n\ninline void add(int U,int V,int W,int C){\n\te[++et]=(ee){V,W,C,h[U]};\n\th[U]=et;\n\te[++et]=(ee){U,0,-C,h[V]};\n\th[V]=et;\n}\n\/\/mp[i][j]\u8868\u793a\u7b2ci\u79cd\u83dc\u7531\u7b2cj\u540d\u53a8\u5e08\u505a\u9700\u8981\u6d88\u8017\u7684\u65f6\u95f4\u3002 \nint n,m,s,t,sm,vis[90005],dis[90005],val[90005],fa[90005],nw[90005],po[45],mp[45][105];\nint q[90005];\nint l,r;\ninline bool SPFA(){\n\tfor(int i=1;i<=t;++i){\n\t\tvis[i]=0,dis[i]=INF,val[i]=INF;\n\t}\n\tdis[s]=0,vis[s]=1,fa[t]=-1;\n\tl=1,r=0;\n\tq[++r]=s;\n\tregister int p;\n\twhile(l<=r){\n\t\tp=q[l++];\n\t\tvis[p]=0;\n\t\tfor(register int i=h[p];i>=0;i=e[i].nxt){\n\t\t\tif(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){\n\t\t\t\tdis[e[i].v]=dis[p]+e[i].c;\n\t\t\t\tfa[e[i].v]=p;\n\t\t\t\tnw[e[i].v]=i;\n\t\t\t\tval[e[i].v]=Min(val[p],e[i].w);\n\t\t\t\tif(!vis[e[i].v]){\n\t\t\t\t\tvis[e[i].v]=1;\n\t\t\t\t\tq[++r]=e[i].v;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn fa[t]!=-1;\n}\n\/\/\u5012\u6570\u7b2cI\u4e2a\uff0c\u53a8\u5e08J \nint ans;\ninline void EK(){\n\tregister int p,cnt,ck;\n\twhile(SPFA()){\n\t\tcnt=fa[t]%sm,ck=fa[t]\/sm+1;\n\t\t++cnt;\n\t\t\/\/\u6ce8\u610f\u8fd9\u91cc\u7684\u9006hash \n\t\tfor(int i=1;i<=n;++i){\n\t\t\tadd(calc2(i),calc(cnt,ck),1,cnt*mp[i][ck]);\n\t\t}\n\t\tp=t;\n\t\tans+=val[t]*dis[t];\n\t\twhile(p!=s){\n\t\t\te[nw[p]].w-=val[t];\n\t\t\te[nw[p]^1].w+=val[t];\n\t\t\tp=fa[p];\n\t\t}\n\t}\n}\nvoid init(){\n\tputs(\"2333\");\n\tn=IO::fri(),m=IO::fri();\n\tfor(int i=1;i<=n;++i){\n\t\tpo[i]=IO::fri();\n\t\tsm+=po[i];\n\t}\n\ts=sm*m+n+1,t=sm*m+n+2;\n\tfor(register int i=1;i<=t;++i){\n\t\th[i]=-1;\n\t}\n\tfor(register int i=1;i<=n;++i){\n\t\tfor(register int j=1;j<=m;++j){\n\t\t\tmp[i][j]=IO::fri();\n\t\t\tadd(calc2(i),calc(1,j),1,mp[i][j]);\n\t\t}\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tadd(s,calc2(i),po[i],0);\n\t}\n\tfor(register int i=1;i<=sm*m;++i){\n\t\tadd(i,t,1,0);\n\t}\n\tEK();\n\tprintf(\"%d\\n\",ans);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u8fd9\u4e00\u9898\u662fSCOI2007\u4fee\u8f66\u7684\u5a01\u529b\u52a0\u5f3a\u7248\u3002 \u7528\u5e38\u89c4\u7684\u5199\u6cd5\u663e\u7136\u662f\u65e0\u6cd5\u901a\u8fc7\u7684\u3002 \u6211\u4eec\u8003\u8651\u52a8\u6001\u52a0\u8fb9\u3002 \u8fd9\u6837\u5c31\u53ef\u4ee5\u6700\u5c0f … <\/p>\n