{"id":186,"date":"2010-03-24T16:49:00","date_gmt":"2010-03-24T08:49:00","guid":{"rendered":"http:\/\/localhost\/?p=186"},"modified":"2010-03-24T16:49:00","modified_gmt":"2010-03-24T08:49:00","slug":"cqoi2009_dance_dance","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=186","title":{"rendered":"[CQOI2009]dance\u8df3\u821e"},"content":{"rendered":"\n

[CQOI2009]dance\u8df3\u821e <\/p>\n

Time Limit:10000MS Memory Limit:165536K
Total Submit:35 Accepted:19
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u4e00\u6b21\u821e\u4f1a\u6709n\u4e2a\u7537\u5b69\u548cn\u4e2a\u5973\u5b69\u3002\u6bcf\u9996\u66f2\u5b50\u5f00\u59cb\u65f6\uff0c\u6240\u6709\u7537\u5b69\u548c\u5973\u5b69\u6070\u597d\u914d\u6210n\u5bf9\u8df3\u4ea4\u8c0a\u821e\u3002\u6bcf\u4e2a\u7537\u5b69\u90fd\u4e0d\u4f1a\u548c\u540c\u4e00\u4e2a\u5973\u5b69\u8df3\u4e24\u9996\uff08\u6216\u66f4\u591a\uff09\u821e\u66f2\u3002
\u6709\u4e00\u4e9b\u7537\u5b69\u5973\u5b69\u76f8\u4e92\u559c\u6b22\uff0c\u800c\u5176\u4ed6\u76f8\u4e92\u4e0d\u559c\u6b22\uff08\u4e0d\u4f1a“\u5355\u5411\u559c\u6b22”\uff09\u3002\u6bcf\u4e2a\u7537\u5b69\u6700\u591a\u53ea\u613f\u610f\u548ck\u4e2a\u4e0d\u559c\u6b22\u7684\u5973\u5b69\u8df3\u821e\uff0c\u800c\u6bcf\u4e2a\u5973\u5b69\u4e5f\u6700\u591a\u53ea\u613f\u610f\u548ck\u4e2a\u4e0d\u559c\u6b22\u7684\u7537\u5b69\u8df3\u821e\u3002
\u7ed9\u51fa\u6bcf\u5bf9\u7537\u5b69\u5973\u5b69\u662f\u5426\u76f8\u4e92\u559c\u6b22\u7684\u4fe1\u606f\uff0c\u821e\u4f1a\u6700\u591a\u80fd\u6709\u51e0\u9996\u821e\u66f2\uff1f <\/p>\n

Input <\/strong><\/p>\n

\u7b2c\u4e00\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570n\u548ck\u3002\u4ee5\u4e0bn\u884c\u6bcf\u884c\u5305\u542bn\u4e2a\u5b57\u7b26\uff0c\u5176\u4e2d\u7b2ci\u884c\u7b2cj\u4e2a\u5b57\u7b26\u4e3a’Y’\u5f53\u4e14\u4ec5\u5f53\u7537\u5b69i\u548c\u5973\u5b69j\u76f8\u4e92\u559c\u6b22\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u4ec5\u4e00\u4e2a\u6570\uff0c\u5373\u821e\u66f2\u6570\u76ee\u7684\u6700\u5927\u503c\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Hint <\/strong><\/p>\n

N<=50
K<=30<\/p>\n

Source
\u7f51\u7edc\u6d41\u5efa\u6a21\u771f\u662f\u8d8a\u6765\u8d8a\u5f97\u5fc3\u5e94\u624b\u4e86(*^__^*) \u3002\u3002\u8fd9\u9053\u9898\u76ee\u5f88\u663e\u7136\u662f\u8981\u6700\u4f18\u8f6c\u5224\u5b9a\u7684\uff0c\u6bd4\u5982\u5224\u5b9a\u80fd\u4e0d\u80fd\u6709T\u8f6e\uff0c\u600e\u4e48\u8f6c\u5462\uff0c\u5bf9\u6bcf\u4e2a\u7537\u751f\u5efa\u7acb3\u4e2a\u5b9a\u70b9\u8868\u793a\u5168\u4f53\uff0c\u5f97\u5230\u559c\u6b22\u7684\uff0c\u5f97\u5230\u4e0d\u559c\u6b22\u7684\uff0c\u90a3\u4e48\u6e90\u5411\u5168\u4f53\u8fde\u4e00\u6761\u5bb9\u91cf\u4e3aT\u7684\u8fb9\uff0c\u5168\u4f53\u5411\u559c\u6b22\u7684\u8fde\u65e0\u7a77\u5927\u7684\u8fb9\uff0c\u5168\u4f53\u5411\u4e0d\u559c\u6b22\u7684\u8fde\u5bb9\u91cf\u4e3ak\u7684bian\uff0c\u7136\u540e\u5973\u751f\u4e5f\u7c7b\u4f3c\u5206\u4e3a3\u4e2a\u8ddf\u6c47\u8fde\uff0c\u7136\u540e\u7537\u751f\u7528\u559c\u6b22\u8282\u70b9\u5411\u559c\u6b22\u7684\u5973\u751f\u7684\u559c\u6b22\u8282\u70b9\uff0c\u7528\u4e0d\u559c\u6b22\u8282\u70b9\u5411\u4e0d\u559c\u6b22\u7684\u5973\u751f\u7684\u4e0d\u559c\u6b22\u8282\u70b9\u8fde\u5bb9\u91cf\u4e3a1\u8fde\u8fb9\u3002\u3002\u5c31OK\u4e86\u3002\u3002
Code\uff1a
<\/strong><\/p>\n

#include<cstdio>#include<queue>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=300+20;struct Edge{ int t,c; Edge(int _t,int _c,Edge* _next): t(_t),next(_next),c(_c){} Edge*next,*op;}*E[maxn]={0};int n,vs,vt;int h[maxn],vh[maxn],v;void InsEdge(int s,int t,int c){ \/\/cout<<s<<" "<<t<<" "<<c<<endl; E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,0,E[t]); E[s]->op=E[t];E[t]->op=E[s];}const int All=0,Like=1,DontLike=2,inf=1<<20;inline int Boy(int x,int type){return x*3+type;}inline int Girl(int x,int type){return (n+x)*3+type;}void Init(){ int k;char x; scanf("%d %dn",&n,&k); v=n*6+2;vs=v-1;vt=v-2; rep(i,n)rep(j,n) { scanf("%cn",&x); int t=x==’Y’?Like:DontLike; InsEdge(Boy(i,t),Girl(j,t),1); } rep(i,n) { InsEdge(vs,Boy(i,All),0); InsEdge(Boy(i,All),Boy(i,Like),inf); InsEdge(Boy(i,All),Boy(i,DontLike),k); InsEdge(Girl(i,All),vt,0); InsEdge(Girl(i,Like),Girl(i,All),inf); InsEdge(Girl(i,DontLike),Girl(i,All),k); }}int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}int CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}void Work(){ int Flow=0; for(int i=1;;i++) { for(Edge*e=E[vs];e;e=e->next)e->c++; for(Edge*e=E[vt];e;e=e->next)e->op->c++; Flow+=CalFlow(); if(Flow!=i*n) { cout<<i-1<<endl; break; } }}int main(){ \/\/freopen("in","r",stdin); Init(); Work();}33 0YYYYYYYYY <\/p>\n","protected":false},"excerpt":{"rendered":"

[CQOI2009]dance\u8df3\u821e Time Limit:10000MS Memory Limit:165536KTotal Submit:35 Accepted:19 Case Time Limit:1000MS Description \u4e00\u6b21\u821e\u4f1a\u6709n\u4e2a\u7537\u5b69\u548cn\u4e2a\u5973\u5b69\u3002\u6bcf\u9996\u66f2\u5b50\u5f00\u59cb\u65f6\uff0c\u6240\u6709\u7537\u5b69\u548c\u5973\u5b69\u6070\u597d\u914d\u6210n\u5bf9\u8df3\u4ea4\u8c0a\u821e\u3002\u6bcf\u4e2a\u7537\u5b69\u90fd\u4e0d\u4f1a\u548c\u540c\u4e00\u4e2a\u5973\u5b69\u8df3\u4e24\u9996\uff08\u6216\u66f4\u591a\uff09\u821e\u66f2\u3002 \u6709\u4e00\u4e9b\u7537\u5b69\u5973\u5b69\u76f8\u4e92\u559c\u6b22\uff0c\u800c\u5176\u4ed6\u76f8\u4e92\u4e0d\u559c\u6b22\uff08\u4e0d\u4f1a“\u5355\u5411\u559c\u6b22”\uff09\u3002\u6bcf\u4e2a\u7537\u5b69\u6700\u591a\u53ea\u613f\u610f\u548ck\u4e2a\u4e0d\u559c\u6b22\u7684\u5973\u5b69\u8df3\u821e\uff0c\u800c\u6bcf\u4e2a\u5973\u5b69\u4e5f\u6700\u591a\u53ea\u613f\u610f\u548ck\u4e2a\u4e0d\u559c\u6b22\u7684\u7537\u5b69\u8df3\u821e\u3002 \u7ed9\u51fa\u6bcf\u5bf9\u7537\u5b69\u5973\u5b69\u662f\u5426\u76f8\u4e92\u559c\u6b22\u7684\u4fe1\u606f\uff0c\u821e\u4f1a\u6700\u591a\u80fd\u6709\u51e0\u9996\u821e\u66f2\uff1f Input \u7b2c\u4e00\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570n\u548ck\u3002\u4ee5\u4e0bn\u884c\u6bcf\u884c\u5305\u542bn\u4e2a\u5b57\u7b26\uff0c\u5176\u4e2d\u7b2ci\u884c\u7b2cj\u4e2a\u5b57\u7b26\u4e3a’Y’\u5f53\u4e14\u4ec5\u5f53\u7537\u5b69i\u548c\u5973\u5b69j\u76f8\u4e92\u559c\u6b22\u3002 Output \u4ec5\u4e00\u4e2a\u6570\uff0c\u5373\u821e\u66f2\u6570\u76ee\u7684\u6700\u5927\u503c\u3002 Sample Input Sample Output Hint N<=50 K<=30 Source \u7f51\u7edc\u6d41\u5efa\u6a21\u771f\u662f\u8d8a\u6765\u8d8a\u5f97\u5fc3\u5e94\u624b\u4e86(*^__^*) \u3002\u3002\u8fd9\u9053\u9898\u76ee\u5f88\u663e\u7136\u662f\u8981\u6700\u4f18\u8f6c\u5224\u5b9a\u7684\uff0c\u6bd4\u5982\u5224\u5b9a\u80fd\u4e0d\u80fd\u6709T\u8f6e\uff0c\u600e\u4e48\u8f6c\u5462\uff0c\u5bf9\u6bcf\u4e2a\u7537\u751f\u5efa\u7acb3\u4e2a\u5b9a\u70b9\u8868\u793a\u5168\u4f53\uff0c\u5f97\u5230\u559c\u6b22\u7684\uff0c\u5f97\u5230\u4e0d\u559c\u6b22\u7684\uff0c\u90a3\u4e48\u6e90\u5411\u5168\u4f53\u8fde\u4e00\u6761\u5bb9\u91cf\u4e3aT\u7684\u8fb9\uff0c\u5168\u4f53\u5411\u559c\u6b22\u7684\u8fde\u65e0\u7a77\u5927\u7684\u8fb9\uff0c\u5168\u4f53\u5411\u4e0d\u559c\u6b22\u7684\u8fde\u5bb9\u91cf\u4e3ak\u7684bian\uff0c\u7136\u540e\u5973\u751f\u4e5f\u7c7b\u4f3c\u5206\u4e3a3\u4e2a\u8ddf\u6c47\u8fde\uff0c\u7136\u540e\u7537\u751f\u7528\u559c\u6b22\u8282\u70b9\u5411\u559c\u6b22\u7684\u5973\u751f\u7684\u559c\u6b22\u8282\u70b9\uff0c\u7528\u4e0d\u559c\u6b22\u8282\u70b9\u5411\u4e0d\u559c\u6b22\u7684\u5973\u751f\u7684\u4e0d\u559c\u6b22\u8282\u70b9\u8fde\u5bb9\u91cf\u4e3a1\u8fde\u8fb9\u3002\u3002\u5c31OK\u4e86\u3002\u3002Code\uff1a #include<cstdio>#include<queue>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=300+20;struct Edge{ int t,c; Edge(int _t,int _c,Edge* _next): t(_t),next(_next),c(_c){} Edge*next,*op;}*E[maxn]={0};int n,vs,vt;int h[maxn],vh[maxn],v;void InsEdge(int s,int t,int c){ \/\/cout<<s<<" "<<t<<" "<<c<<endl; E[s]=new […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/186"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=186"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/186\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=186"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=186"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}