额。。VIJOS复活了。。所以我去A了这道题。。www.vijos.cn/Problem_Show.asp
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。 相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然 后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。我感觉应该会很快，没想到0ms秒杀，爽额。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000+1,maxp=maxn>>3;
bool NotPrime[maxn]={0};
int Ps[maxp],cnt=0;
void GetPrime()
{
for(int i=2;i*i<maxn;i++)
{
if(!NotPrime[i])
{
for(int j=i*2;j<maxn;j+=i)
NotPrime[j]=true;
}
}
for(int i=2;i<maxn;i++)
if(!NotPrime[i])
Ps[cnt++]=i;
}
int Max[maxp],pnt,Tmp[1000];
void GetDiv(int p)
{
pnt=0;
for(int i=0;i<cnt;i++)
{
int t=Ps[i];if(t*t>p)break;
if(p%t==0)
{
Tmp[pnt++]=i;
while(p%t==0)p/=t;
}
}
if(p!=1)
{
int i=lower_bound(Ps,Ps+cnt,p)-Ps;
Tmp[pnt++]=i;
}
}
void solve()
{
int n,x;scanf("%d",&n);
while(n–)
{
scanf("%d",&x);
GetDiv(x);
int ret=0;
rep(i,pnt)ret=max(ret,Max[Tmp[i]]);
ret++;
rep(i,pnt) Max[Tmp[i]]=ret;
}
int ans=0;
rep(i,cnt) ans=max(ans,Max[i]);
printf("%dn",ans);
}
int main()
{
//freopen("in","r",stdin);
GetPrime();
solve();
}
Category Archives: DefaultCategory
[HAOI2008]硬币购物
[HAOI2008]硬币购物
Time Limit:10000MS Memory Limit:165536K
Total Submit:11 Accepted:8
Case Time Limit:1000MS
Description
硬币购物
一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。
每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
Input
第一行
c1,c2,c3,c4,tot
下面tot行
d1,d2,d3,d4,s
Output
每次的方法数
Sample Input
Sample Output
Source
这题有点NB的，DP+容斥原理囧。。
Code:
#include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; else ret+=Dp[now]; return; } dfs(p+1,ch+1,now-C[p]*(D[p]+1),ret); dfs(p+1,ch,now,ret);}void solve(){ int s;ll ans=0;for(int i=0;i<maxn;i++)cin>>D[i]; cin>>s; dfs(0,0,s,ans); cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); int t; for(int i=0;i<maxn;i++)cin>>C[i];cin>>t; Cal(); while(t–)solve();}427数据规模di,s<=100000tot<=10001 2 5 10 23 2 3 1 101000 2 2 2 900
[CQOI2009]dance跳舞
[CQOI2009]dance跳舞
Time Limit:10000MS Memory Limit:165536K
Total Submit:35 Accepted:19
Case Time Limit:1000MS
Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。
给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。
Output
仅一个数，即舞曲数目的最大值。
Sample Input
Sample Output
Hint
N<=50
K<=30
Source
网络流建模真是越来越得心应手了(*^__^*) 。。这道题目很显然是要最优转判定的，比如判定能不能有T轮，怎么转呢，对每个男生建立3个定点表示全体，得到喜欢的，得到不喜欢的，那么源向全体连一条容量为T的边，全体向喜欢的连无穷大的边，全体向不喜欢的连容量为k的bian，然后女生也类似分为3个跟汇连，然后男生用喜欢节点向喜欢的女生的喜欢节点，用不喜欢节点向不喜欢的女生的不喜欢节点连容量为1连边。。就OK了。。
Code：
#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
[AHOI2006]上学路线route
很显然首先spfa出最短路，然后就按最短路建图，然后很显然就换成了最小割的问题了囧。。不过这里的割是有向的，注意一下哦(*^__^*) 嘻嘻
Code:
#include<cstdio>#include<queue>#include<algorithm>#include<iostream>using namespace std;const int maxn=500;struct Edge{ int t,c,Len; bool e; Edge(int _t,int _Len,int _c,Edge* _next): t(_t),Len(_Len),next(_next),c(_c),e(false){} Edge*next,*op; /*void addFlow(int _c) { c-=_c; op->c+=_c; }*/}*E[maxn];int n,m,vs,vt;void InsEdge(int s,int t,int c,int Len){ E[s]=new Edge(t,Len,c,E[s]); E[t]=new Edge(s,Len,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}void Init(){ scanf("%d %d",&n,&m);int s,t,Len,c; vs=0,vt=n-1; while(m–) { scanf("%d %d %d %d",&s,&t,&Len,&c); InsEdge(s-1,t-1,c,Len); }}const int inf=~0U>>2;int DistToStart[maxn],DistToEnd[maxn];void Spfa(int Dist[maxn],int vs){ queue<int> Q; bool inQ[maxn]={0}; for(int i=0;i<n;i++) Dist[i]=inf; Dist[vs]=0;inQ[vs]=true;Q.push(vs); while(Q.size()) { int t=Q.front();Q.pop();inQ[t]=false;int cost=Dist[t]; for(Edge*i=E[t];i;i=i->next) { int ncost=cost+i->Len; if(ncost<Dist[i->t]) { Dist[i->t]=ncost; if(!inQ[i->t]) inQ[i->t]=true,Q.push(i->t); } } }}void BuildGraph(){ Spfa(DistToStart,vs); Spfa(DistToEnd,vt); int cost=DistToStart[vt]; for(int i=0;i<n;i++) for(Edge*e=E[i];e;e=e->next) if(DistToStart[i]+e->Len+DistToEnd[e->t]==cost) { e->e=true; e->op->e=true; e->op->c=0; } cout<<cost<<endl;}int h[maxn],vh[maxn],v;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->e&&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->e&&i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}long long CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); v=n;vh[0]=v;long long flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}int main(){ //freopen("in","r",stdin); Init(); BuildGraph(); cout<<CalFlow()<<endl;}
[SCOI2005]最大子矩阵
[SCOI2005]最大子矩阵
Time Limit:10000MS Memory Limit:165536K
Total Submit:26 Accepted:13
Case Time Limit:1000MS
Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
Sample Output
Source
这个明显要DP，一维的太水就不说了。
二维的话，首先预处理出子矩阵的和比较方便。
设Dp(i,a1,a2)为i个矩形，第1列1..a1，第二列1..a2的最大价值，
那么如果第一列的a1不放的话，是Dp(i,a1-1,a2)。。。
如果第二列的a2不放的话，是Dp(i,a1,a2-1)。。。
如果放的话枚举上一个状态是O（n）的。
然后只有在a1==a2的时候才枚举宽度为2的矩阵的情况就可以了。。
不过细节很要紧，我WA了半天，这样下去怎么行啊。比赛考到的话肯定悲剧的囧。。
Code：
#include<iostream>#include<cstring>using namespace std;const int maxn=100+10,maxk=10+1,inf=~0U>>2;int n,m,k;//solve 1inline void Renew(int&x,int c){ x=max(x,c);}void Solve1(){ int Dp[maxk][maxn]={0}; int A[maxn]={0}; for(int i=1;i<=n;i++)cin>>A[i],A[i]+=A[i-1]; for(int i=1;i<=k;i++) { for(int j=0;j<=n;j++) { int&x=Dp[i][j];x=-inf; if(j)x=Dp[i][j-1]; for(int o=0;o<j;o++) { Renew(x,Dp[i-1][o]+A[j]-A[o]); } } } cout<<Dp[k][n]<<endl;}//solve 2void Solve2(){ int Dp[maxk][maxn][maxn]={0}; int A[2][maxn]={0},S[maxn]={0}; for(int j=1;j<=n;j++) for(int i=0;i<2;i++) cin>>A[i][j],S[j]+=A[i][j],A[i][j]+=A[i][j-1]; for(int j=1;j<=n;j++) S[j]+=S[j-1]; for(int i=1;i<=k;i++) for(int a1=0;a1<=n;a1++) for(int a2=0;a2<=n;a2++) { int&x=Dp[i][a1][a2];x=-inf; if(a1) { Renew(x,Dp[i][a1-1][a2]); for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][a2]+A[0][a1]-A[0][o]); } if(a2) { Renew(x,Dp[i][a1][a2-1]); for(int o=0;o<a2;o++) Renew(x,Dp[i-1][a1][o]+A[1][a2]-A[1][o]); } if(a1==a2) { for(int o=0;o<a1;o++) Renew(x,Dp[i-1][o][o]+S[a1]-S[o]); } } cout<<Dp[k][n][n]<<endl;}int main(){ //freopen("in","r",stdin); cin>>n>>m>>k; if(m==1)Solve1(); else Solve2();}93 2 21 -32 3-2 3
[HNOI2005]虚拟内存
[HNOI2005]虚拟内存
Time Limit:50000MS Memory Limit:165536K
Total Submit:16 Accepted:6
Case Time Limit:5000MS
Description
操作系统中一种重要的存储管理技术就是虚拟内存技术。操作系统中允许进程同时运行，也就是并行。每个进程都有其相对独立的数据块（进程运行的过程中将对其进行读写操作）。理想的情况下，这些数据块都应该存放在内存中，这样才能实现高效的读写操作。但事实上，内存的容量有限，每个进程只能把一部分数据放在内存中，为了解决这个矛盾，提出了虚拟内存技术。
虚拟内存技术的基本原理是：对进程而言，内存空间是无限大的，进程可以随意地读写数据，而对操作系统内部而言，利用外存来模拟扩充的内存空间，进程要求访问某个内存单元时，交由操作系统处理，操作系统首先在内存中查找该单元是否存在，如果存在，查找成功，否则转入外存查找（一定存在于外存中）。
就存储介质的物理性质而言，内存的访问速度相对于外存要快得多，因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中，而把那些访问次数很少的数据放在外存中。如何选择内存中暂留的数据是一个很值得研究的问题，下面介绍一个内存管理中比较常用的算法：
内存中的数据以页为基本存储单位，进程的读写操作都针对页来进行。实际内存空间被分割成n页，虚拟内存空间的页数往往要多得多。某一时刻，进程需要访问虚存编号为P的页，该算法的执行步骤如下：
a. 首先在内存中查找，如果该页位于内存中，查找成功，转d，否则继续下面的操作；
b. 寻找内存中是否存在空页（即没有装载任何数据页的页面），若有，则从外存中读入要查找页，并将该页送至内存中的空页进行存储，然后转d，否则继续下面的操作；
c. 在内存中寻找一个访问次数最少的页面（如果存在多个页面的访问次数同时为最少，则选取最早读入数据进入内存的那个页面），从外存中读入要查找页，替换该页。
d. 结束
所谓访问次数是指从当前页面进入内存到该时刻被访问的次数，如果该页面以前进入过内存并被其它页面替换，那么前面的访问次数不应计入这个时刻的访问次数中。
你的任务是设计一个程序实现上述算法。
测试数据将会提供m条读写内存的命令，每条命题提供要求访问的虚拟内存页的编号P。你的程序要求能够模拟整个m条命令的全部执行过程，所有的命令是按照输入的先后执行的，最开始的时候内存中的n页全为空。
Input
第1行为n<10000和m<1000000，分别表示内存页数和读写内存命令条数。接下来有m行，其中第i+1行有一个正整数Pi<=10^9，表示第i条读写内存命令需要访问的虚拟内存页的编号。
Output
仅包含一个正整数，表示在整个模拟过程中，在内存中直接查找成功的次数（即上面的算法只执行步骤a的次数）。
Sample Input
Sample Output
Source
很显然是一个模拟题。。
饿。这个应该用一个Hash查找id，用一个Heap保存当前内存的状态的，但我直接用了map，结果慢死囧。。
Code：
#include<cstdio>#include<set>#include<map>#include<utility>#include<queue>#include<iostream>using namespace std;typedef pair<int,int> ii;struct state{ int used,first; bool inQ; state(){} state(int _first):used(1),first(_first),inQ(true){}};map<int,state> id;struct node{ int id,used,first; node(const state&s,int _id) { used=s.used;first=s.first; id=_id; } bool operator<(const node&o)const { if(used!=o.used) return o.used<used; return o.first<first; }};int n,m,Time=0,ans=0;priority_queue<node> Q;void Check(){ while(Q.size()>=n) { node t=Q.top();Q.pop(); if(t.used<id[t.id].used) { t.used=id[t.id].used; Q.push(t); } else { state&s=id[t.id]; s.inQ=false; s.used=1; //cout<<"Out"<<t.id<<endl; break; } }}void Insert(int x){ if(id.count(x)) { state&s=id[x]; if(s.inQ) { //cout<<"Great"<<x<<endl; ans++;s.used++;s.first=Time; } else { Check();s.inQ=true;s.first=Time; Q.push(node(s,x)); } } else { state s(Time); id[x]=s; Check(); Q.push(node(s,x)); } //cout<<"In"<<x<<endl;}int main(){ freopen("in","r",stdin); scanf("%d %d",&n,&m);int x; while(m–) { scanf("%d",&x); Insert(x); ++Time; } cout<<ans<<endl;}
Code：
13 8 11234254
[Ahoi2009]chess 中国象棋
[Ahoi2009]chess 中国象棋
Time Limit:10000MS Memory Limit:65536K
Total Submit:21 Accepted:11
Case Time Limit:1000MS
Description
在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。
请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.
Input
一行包含两个整数N，M，中间用空格分开.
Output
输出所有的方案数，由于值比较大，输出其mod 9999973
Sample Input
Sample Output
Hint
除了在3个格子中都放满炮的的情况外，其它的都可以.
100%的数据中N,M不超过100
50%的数据中，N,M至少有一个数不超过8
30%的数据中，N,M均不超过6
Source
Day2
61.187.179.132:8080/JudgeOnline/showproblem
要Dp。。非常的复杂，看Code吧。。累死了。。
Code：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=100+10,mod=9999973;int Dp[2][maxn][maxn],n,m;int C[maxn][maxn]={0};int plus_mod(int&a,int b){ a+=b;return a%=mod;}int multi_mod(int&a,int b){ return a=((long long)a*b)%mod;}void GetC(){ C[0][0]=1; for(int i=1;i<=m;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) { C[i][j]=C[i-1][j-1]+C[i-1][j]; C[i][j]%=mod; } }}#define MM(x) memset(x,0,sizeof(x))int main(){ cin>>n>>m;int now=0,next=1; MM(Dp);GetC(); Dp[next][m][0]=1; for(int i=0;i<n;i++) { swap(now,next); MM(Dp[next]); for(int a0=0;a0<=m;a0++) for(int a1=0;a1+a0<=m;a1++) if(Dp[now][a0][a1]) { int x=Dp[now][a0][a1],c; //Dont used Row i plus_mod(Dp[next][a0][a1],x); //Put one if(a0) { c=x; multi_mod(c,C[a0][1]); plus_mod(Dp[next][a0-1][a1+1],c); } if(a1) { c=x; multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0][a1-1],c); } //Put two if(a0>=2) { c=x; multi_mod(c,C[a0][2]); plus_mod(Dp[next][a0-2][a1+2],c); } if(a1>=2) { c=x; multi_mod(c,C[a1][2]); plus_mod(Dp[next][a0][a1-2],c); } if(a0&&a1) { c=x; multi_mod(c,C[a0][1]); multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0-1][a1],c); } } } int ans=0; rep(i,m+1)rep(j,m+1)plus_mod(ans,Dp[next][i][j]); cout<<ans<<endl;}71 3
USACO Telecowmunication
我突然很怀念USACO，去年我A的差不多了就不想A了。。这个月把它A完吧(*^__^*)
这个题目大意nocow上有。。不过我的算法完全是错的居然过了囧。。
很明显是一个最小割的问题，关键是要让字典序最小，
一般来说是要一个个边枚举的删过去的，但是我懒得怎么搞，于是我给每个节点的点权改成了10000+i i表示第i个节点，然后就这样做了。。
结果居然AC了。这数据也太烂了囧。。
Code:
/* PROG: telecow LANG: C++ ID: Tom Chen*/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=200+10;typedef vector<int> vi;struct Edge{ int t,c; Edge*next,*op; Edge(int _t,int _c,Edge* _next):t(_t),c(_c),next(_next){}}*E[maxn]={0};void InsEdge(int s,int t,int c){ 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];}int vs,vt,n,m;int h[maxn],vh[maxn];const int in=0,out=1,off=10000;inline int node(int x,int type){ return x*2+type;}void Init(){ cin>>n>>m>>vs>>vt;vs–;vt–; vs=node(vs,out); vt=node(vt,in); int s,t; rep(i,n) InsEdge(node(i,in),node(i,out),off+i); while(m–) { cin>>s>>t;–s;–t; InsEdge(node(s,out),node(t,in),inf); InsEdge(node(t,out),node(s,in),inf); }}int v;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)); v=n*2;vh[0]=v;int flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}bool Vis[maxn]={0};void dfs(int x){ Vis[x]=true; for(Edge*i=E[x];i;i=i->next)if(i->c&&!Vis[i->t])dfs(i->t);}bool Used(int x){ if (Vis[node(x,in)]&&!Vis[node(x,out)]) return true; return false;}void Work(){ int flow=CalFlow()/off; cout<<flow<<endl; vi Ans; dfs(vs); rep(i,n)if(Used(i)) Ans.pb(i+1); cout<<Ans[0]; for(int i=1;i<Ans.size();i++) cout<<" "<<Ans[i]; cout<<endl;}int main(){ freopen("telecow.in","r",stdin); freopen("telecow.out","w",stdout); Init(); Work();}
囧了。。
衡阳八中的OJMS也挂掉了。。这下连个做中文题的地方都没有了。只好去SGU做英文题了。悲剧大发了囧。。
还是说这个OJ换网址了？有神牛知道么囧。。
SGU 210
210. Beloved Sonstime limit per test: 2 sec.
memory limit per test: 65536 KBinput: standard
output: standard
Once upon a time there lived a king and he had N sons. And the king wanted to marry his beloved sons on the girls that they did love. So one day the king asked his sons to come to his room and tell him whom do they love.
But the sons of the king were all young men so they could not tell exactly whom they did love. Instead of that they just told him the names of the girls that seemed beautiful to them, but since they were all different, their choices of beautiful girls also did not match exactly.
The king was wise. He did write down the information that the children have provided him with and called you, his main wizard.
"I want all my kids to be happy, you know," he told you, "but since it might be impossible, I want at least some of them to marry the girl they like. So please, prepare the marriage list."
Suddenly you recalled that not so long ago the king told you about each of his sons, so you knew how much he loves him. So you decided to please the king and make such a marriage list that the king would be most happy. You know that the happiness of the king will be proportional to the square root of the sum of the squares of his love to the sons that would marry the girls they like.
So, go on, make a list to maximize the king’s happiness.
Input
The first line of the input file contains N — the number of king’s sons (1 ≤ N ≤ 400). The second line contains N integer numbers Ai ranging from 1 to 1000 — the measures of king’s love to each of his sons.
Next N lines contain lists of king’s sons’ preferences — first Ki — the number of the girls the i-th son of the king likes, and then Ki integer numbers — the girls he likes (all potentially beautiful girls in the kingdom were numbered from 1 to N, you know, beautiful girls were rare in those days).
Output
Output N numbers — for each son output the number of the beautiful girl he must marry or 0 if he must not marry the girl he likes.
Denote the set of sons that marry a girl they like by L, then you must maximize the value of
Sample test(s)
Input 4
1 3 2 4
4 1 2 3 4
2 1 4
2 1 4
2 1 4
Output
2 1 0 4
看上去好像是一个最优匹配的问题，可以很显然将所有孩子排个序，然后一个个匹配过去就可以了囧。。
MS那个八中的OJ不能上了囧。。只好A SGU了囧。。
Code：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=400;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;vi E[maxn];int Link[maxn],n;bool Vis[maxn]={0};bool dfs(int x){ if(Vis[x]) return false; Vis[x]=true; tr(i,E[x])if(Link[*i]==-1||dfs(Link[*i])) return Link[*i]=x,true; return false;}int A[maxn];bool cmp(const int&a,const int&b){ return A[a]>A[b];}int main(){ //freopen("in","r",stdin); int P[maxn]; cin>>n; rep(i,n)cin>>A[i],P[i]=i; rep(i,n) { int t,x;cin>>t; while(t–)cin>>x,E[i].pb(x-1); } rep(i,n) Link[i]=-1; sort(P,P+n,cmp); rep(i,n) { memset(Vis,0,sizeof(Vis)); dfs(P[i]); } int Ans[maxn]={0}; rep(i,n) Ans[Link[i]]=i+1; rep(i,n) cout<<Ans[i]<<" "; cout<<endl;}